UVA 11235 - Frequent values (RMQ的基础应用)

题意：给出一个非降序排列的整数数组a[1], a[2], ...... , a[n]，给出一系列询问（i, j），回答a[i], a[i+1], ...... , a[j]中出现最多的值所出现的次数。

思路：典型的RMQ应用，第一次仿着写，将数组游程编码，value[i]和cnt[i]分别表示第i段的数值和出现次数，num[p], left[p], right[p]分别表示位置p所在段的编号和左右端点的位置。则查询（L， R）的结果为以下三部分的最大值：从L到L所在段的结束的个数（right[L]-L+1），从R所在段的开始到R处的个数（R-left[R]+1），中间从num[L]+1到num[R]-1段的count的最大值。如果L和R在同一段，则答案就是R-L+1。

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       using namespace std; const int MAXN = 100010; int dp[MAXN][30],value[MAXN],cnt[MAXN],num[MAXN],left[MAXN],right[MAXN]; int RMQ(int l,int r){ if (r < l) return 0; int k = log(1.0*r-l+1) / log(2.0); return max(dp[l][k],dp[r-(1<