题意：给你一个不下降序列（n <= 1e5），对于每个询问(L,R) （q <= 1e5）找出出现次数最多的数所对应的出现次数。
思路：显然我们对于每个询问我们要做到 O（1）输出，所以我们要做满足这一条件的预处理。
注意序列式不下降的，所以每个数值都是连续的一段，我们可以把这序列压缩。
如 -1 -1 3 3 5 5 5 可以表示成 （-1，2）， （3， 2）， （5， 3） 三段（a，b）a表示数值，b表示个数。
用v[i]和c[i]分别表示第i段的数值和出现的次数，p[j]，l[j]，r[j]分别表示原来序列位置j所在段的编号和左右端点的位置。
对于每个询问（x，y），取左边的一小段和右边(第L段)的一小段其中的最大值（第R段），L,R两段可能是不完整， L段个数为 r[L]-L+1， R段个数为 R-l[R]+1；
中间一段时完整的，中间一段的处理可以先用RMQ预处理出其中个数的最大值。
特别注意：当x，y属于同一段时不属于以上的情况，要另外考虑，其答案就是整段y-x+1。
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
#define maxn 100005
int a[maxn], v[maxn], c[maxn], p[maxn], l[maxn], r[maxn];
int num, n; // num表示有几段。
int LOG[maxn], f[33][maxn];// LOG[n] = log2(n)向下取整，f数组记录RMQ
void rmq_init() {
int i, j;
LOG[0] = -1;
for (i = 1; i < maxn; i++)
LOG[i] = LOG[i >> 1] + 1;
for (i = 1; i <= num; i++)
f[0][i] = c[i];
for (j = 1; j <= LOG[num]; j++) {
int x = num - (1 << j) + 1;
for (i = 1; i <= x; i++) {
int y = i + (1 << j >> 1);
f[j][i] = max(f[j - 1][i], f[j - 1][y]);
}
}
}
int rmq(int l, int r) {
if (l > r) return 0; // 注意这种情况
int k = LOG[(r - l + 1)], y = r - (1 << k) + 1;
return max(f[k][l], f[k][y]);
}
void debug() {
int i, j;
for (i = 1; i <= num; i++)
printf("v[%d] = %d c[%d] = %d\n", i, v[i], i, c[i]);
for (i = 1; i <= n; i++) {
printf("p[%d] = %d l = %d r = %d\n", i, p[i], l[i], r[i]);
}
for (i = 1; i <= num; i++)
for (j = i; j <= num; j++)
printf("[%d, %d] = %d\n", i, j, rmq(i, j));
}
int main() {
int i, j, k, q;
while ( ~scanf("%d", &n) && n) {
scanf("%d", &q);
for (i = 1; i <= n; i++)
scanf("%d", &a[i]);
num = 0;
for (i = 1; i <= n; i++) {
for (j = i; j < n && a[j] == a[j + 1]; j++);
v[++num] = a[i];
c[num] = j - i + 1;
for (k = i; k <= j; k++)
p[k] = num, l[k] = i, r[k] = j;
i = j;
}
rmq_init();
//debug();
int x, y;
while (q--) {
scanf("%d%d", &x, &y);
if(p[x] == p[y]) { printf("%d\n", y-x+1); continue; }
int t = max(r[x] - x + 1, y - l[y] + 1);
//cout << "t = " << t << endl;
printf("%d\n", max(t, rmq(p[x] + 1, p[y] - 1)));
}
}
return 0;
}