Frequent values
You are given a sequence of n integers a1 , a2 , ... , an in non-decreasing order. In addition to that, you are given several queries consisting of indices i and j (1 ≤ i ≤ j ≤ n). For each query, determine the most frequent value among the integers ai , ... , aj.
Input
The input consists of several test cases. Each test case starts with a line containing two integers n and q (1 ≤ n, q ≤ 100000). The next line contains n integers a1 , ... , an (-100000 ≤ ai ≤ 100000, for each i ∈ {1, ..., n}) separated by spaces. You can assume that for each i ∈ {1, ..., n-1}: ai ≤ ai+1. The following q lines contain one query each, consisting of two integers i and j (1 ≤ i ≤ j ≤ n), which indicate the boundary indices for the
query.
The last test case is followed by a line containing a single 0.
Output
For each query, print one line with one integer: The number of occurrences of the most frequent value within the given range.
Sample Input
10 3
-1 -1 1 1 1 1 3 10 10 10
2 3
1 10
5 10
0
Sample Output
1
4
3 这题由于序列非降，所以就可以把整个数组进行游程编码(RLE Run Length Encoding)。
还是很简单的~~~
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
const int maxn=;
int mm[maxn],Max[maxn][];
int MAXL[maxn],MAXR[maxn],cnt=;
int ID[maxn],tot[maxn],a[maxn];
void Init(){
memset(tot,,sizeof(tot));
cnt=;
}
int main(){
#ifndef ONLINE_JUDGE
//freopen(".in","r",stdin);
//freopen(".out","w",stdout);
#endif int n,Q;
while(~scanf("%d",&n)&&n){
scanf("%d",&Q);
Init();
for(int i=;i<=n;i++)
scanf("%d",&a[i]);
a[]=a[n+]=-;
for(int i=;i<=n;i++){
if(a[i]==a[i-]){
MAXL[i]=MAXL[i-];
ID[i]=ID[i-];
}
else{
MAXL[i]=i;
ID[i]=++cnt;
}
tot[ID[i]]++;
}
//MAXL[i]指与a[i]相等的1~i-1中最靠左的位置
//ID[i]指当前位置被分到第几块
//tot[i]指第i块的长度
for(int i=n;i>=;i--){
if(a[i]==a[i+])
MAXR[i]=MAXR[i+];
else
MAXR[i]=i;
}
//MAXR[i]指与a[i]相等的i+1~n中最靠右的位置
mm[]=-;
for(int i=;i<=cnt;i++){
mm[i]=(i&(i-))?mm[i-]:mm[i-]+;
Max[i][]=tot[i];
}
for(int k=;k<=mm[cnt];k++)
for(int i=;i+(<<k)-<=cnt;i++)
Max[i][k]=max(Max[i][k-],Max[i+(<<(k-))][k-]);
//对块处理出稀疏表
int a,b,ans;
while(Q--){
scanf("%d%d",&a,&b);
if(a>b)swap(a,b);
if(ID[a]==ID[b]){
printf("%d\n",b-a+);
continue;
}
ans=-;
ans=max(MAXR[a]-a+,b-MAXL[b]+);
a=ID[MAXR[a]+];
b=ID[MAXL[b]-];
if(a<=b)
ans=max(ans,max(Max[a][mm[b-a+]],Max[b-(<<mm[b-a+])+][mm[b-a+]]));
printf("%d\n",ans);
}
}
return ;
}