给定一个长度为n的非递减序列： a 1 , a 2 , . . . , a n a 1 ​ ,a 2 ​ ,...,a n ​ 。

有q个询问：

每个询问给出两个数a b：要求查询[a, b]区间内的众数的出现次数。

注：众数就是区间内出现最多次数的数字，如果有多个任意取一个即可。

第一行包含两个整数n和q。（<=1e5）

第二行有n个整数 a。(-1e5~1e5)

接下来q行，每行给出整数 a,b。（a<=b<=n）

我的代码

#include <bits/stdc++.h>
using namespace std;
int n, m, tot, lo[110000], dp[110000][20];
int a[110000], b[1100000], is[110000], f[110000], t[110000];
void init() {
	//lo[i]=t表示最小的t使2的t次方<=i
	lo[0] = -1;
	for (int i = 1; i <= tot; i++) {
		lo[i] = lo[i >> 1] + 1;
	}
	for (int i = 1; i <= tot; i++) {
		dp[i][0] = b[i];
		//i~i+2^0-1
		//即i~i区间的最小值为a[i]
	}
	for (int i = 1; i < 20; i++) {
		for (int j = 1; j + (1 << i) - 1 <= tot; j++) {
			//j~j+2^i-1可以由j~j+2^(i-1)-1 
			//和j+2^(i-1)~(j+2^(i-1))+2^(i-1)-1转来 
			dp[j][i] = max(dp[j][i - 1], dp[j + (1 << (i - 1))][i - 1]);
		}
	}
}
int ask(int l, int r) {
	if (l > r) return 0;
	int x = r - l + 1;
	int k = lo[x];//最小的一个k使2^k<=x
	return min(dp[l][k], dp[r - (1 << k) + 1][k]);
} 
int main() {
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; i++) {
		scanf("%d", &a[i]);
		is[i] = a[i] == a[i - 1] ? tot : ++tot;
		b[tot]++;
		f[tot] = i;
		if (!t[tot]) t[tot] = i;
	}
	init();
	while (m--) {
		int x, y;
		scanf("%d%d", &x, &y);
		int ans = 0;
		ans = max(f[is[x]] - x + 1, y - t[is[y]] + 1);
		ans = max(ans, ask(is[x] + 1, is[y] - 1));
		printf("%d\n", ans);
	}
	return 0;
}

WA & 35 pts。