题目大意：有$n(n\leqslant5\times10^5)$个数，$m(m\leqslant5\times10^5)$个询问，每个询问问区间$[l,r]$中众数的出现次数
题解：分块，设块大小为$S$，先可以预处理出两两块之间的众数出现次数，复杂度$O(\Big(\dfrac n S\Big)n)$。询问时先把答案设成整块内的答案，然后对两边剩下的最多$2S$个元素进行讨论。
难点在如何快速求出一个元素在区间内出现次数，先想到的是主席树，但是多了一个$\log_2$，并过不去。可以把每种数出现的位置用$vector$存下来，并且对每个数存一个它在$vector$中的位置，第$i$个数的位置是$ret_i$，假设现在的答案为$ans$，正在处理左边的多余元素，处理到第$i$个，可以看这个数值的$vector$中，第$ret_i+ans$位是否小于$r$，若小于，则这个数至少出现了$ans+1$次，更新答案。右边也是类似的。
发现$ans$最多自增$2S$次，所以一次查询的复杂度是$O(2S)$的，总复杂度为$O(2Sm+\Big(\dfrac n S\Big)n)$，当$S$略小于$\sqrt n$时最优（其实是我不怎么算）
卡点：$Ynoi$当然卡常啦
C++ Code：
#include <algorithm>
#include <cstdio>
#include <cctype>
#include <vector> namespace std {
struct istream {
#define M (1 << 24 | 3)
char buf[M], *ch = buf - 1;
inline istream() {
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
#endif
fread(buf, 1, M, stdin);
}
inline istream& operator >> (int &x) {
while (isspace(*++ch));
for (x = *ch & 15; isdigit(*++ch); ) x = x * 10 + (*ch & 15);
return *this;
}
#undef M
} cin;
struct ostream {
#define M (1 << 24 | 3)
char buf[M], *ch = buf - 1;
int w;
inline ostream& operator << (int x) {
if (!x) {
*++ch = '0';
return *this;
}
for (w = 1; w <= x; w *= 10);
for (w /= 10; w; w /= 10) *++ch = (x / w) ^ 48, x %= w;
return *this;
}
inline ostream& operator << (const char x) {*++ch = x; return *this;}
inline ostream& operator << (const char *x) {
while (*x) *this << *x++;
return *this;
}
inline ~ostream() {
#ifndef ONLINE_JUDGE
freopen("output.txt", "w", stdout);
#endif
fwrite(buf, 1, ch - buf + 1, stdout);
}
#undef M
} cout;
} #define maxn 500010
const int BSZ = 610, BNUM = maxn / BSZ + 10; int cnt[maxn];
int MAX[BNUM][BNUM];
int L[maxn], R[maxn], bel[maxn]; int n, m, Bnum;
int w[maxn], v[maxn]; std::vector<int> list[maxn];
int ret[maxn];
int main() {
std::cin >> n >> m;
for (int i = 1; i <= n; i++) {
std::cin >> w[i];
v[i] = w[i];
bel[i] = (i - 1) / BSZ + 1;
} const int tot = (std::sort(v + 1, v + n + 1), std::unique(v + 1, v + n + 1) - v - 1);
for (int i = 1; i <= n; i++) {
w[i] = std::lower_bound(v + 1, v + tot + 1, w[i]) - v;
ret[i] = list[w[i]].size();
list[w[i]].push_back(i);
} Bnum = bel[n];
for (int i = 1; i <= Bnum; i++) {
L[i] = (i - 1) * BSZ, R[i] = L[i] + BSZ - 1;
}
L[1] = 1, R[Bnum] = n;
for (int i = 1; i <= Bnum; i++) {
__builtin_memset(cnt, 0, sizeof cnt);
int Max = 0, now = i;
for (int j = L[i]; j <= n; j++) {
cnt[w[j]]++;
Max = std::max(Max, cnt[w[j]]);
if (j == R[now]) {
MAX[i][now] = Max;
now++;
}
}
} int ans = 0;
while (m --> 0) {
int l, r;
std::cin >> l >> r;
l ^= ans, r ^= ans;
const int lb = bel[l], rb = bel[r];
ans = 0;
if (lb == rb) {
for (int i = l; i <= r; i++) {
const int W = w[i], sz = list[W].size(), pos = ret[i];
while (pos + ans < sz && list[W][pos + ans] <= r) ans++;
}
} else {
if (lb + 1 < rb) ans = MAX[lb + 1][rb - 1];
for (int i = l; i <= R[lb]; i++) {
const int W = w[i], sz = list[W].size(), pos = ret[i];
while (pos + ans < sz && list[W][pos + ans] <= r) ans++;
}
for (int i = L[rb]; i <= r; i++) {
const int W = w[i], pos = ret[i];
while (pos >= ans && list[W][pos - ans] >= l) ans++;
}
}
std::cout << ans << '\n';
}
return 0;
}