题意
给定序列 \(s\)，每次询问 \(l, r\) 的区间众数的出现次数。
强制在线。空间：\(62.5MB\)。
Sol
蒲公英卡常卡空间版。
考虑优化那个 \(n \times m\) 的数组。
我们要求 \(l, r\) 之中某个数的个数。
乍一看不好弄，仔细想想就会发现，如果我们知道当前的最优答案。在长常数时间内就能知道当前散块是否比最优答案更优。
考虑将每个数按照下标扔进 \(n\) 个 \(vector\)。
直接暴力查询 \(p_x + ans\) 即可。
不难发现，该算法的时间复杂度是正确的。
Code
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <array>
#include <queue>
#include <vector>
#include <cassert>
#define pii pair <int, int>
using namespace std;
#ifdef ONLINE_JUDGE
#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)
char buf[1 << 23], *p1 = buf, *p2 = buf, ubuf[1 << 23], *u = ubuf;
#endif
int read() {
int p = 0, flg = 1;
char c = getchar();
while (c < '0' || c > '9') {
if (c == '-') flg = -1;
c = getchar();
}
while (c >= '0' && c <= '9') {
p = p * 10 + c - '0';
c = getchar();
}
return p * flg;
}
void write(int x) {
if (x < 0) {
x = -x;
putchar('-');
}
if (x > 9) {
write(x / 10);
}
putchar(x % 10 + '0');
}
#define rg register
#define il inline
#define fi first
#define se second
const int N = 5e5 + 10, M = 1505;
array <int, N> s, h;
namespace Blk {
int bsi = 433;
il int calc(rg int x) {
return (x - 1) / bsi + 1;
}
array <int, N> cur;
queue <int> q;
int tot;
il void add(rg int x, rg int y) {
if (!x) return;
cur[x] += y;
q.push(x);
if (cur[x] > cur[tot]) tot = x;
else if (cur[x] == cur[tot]) tot = min(tot, x);
}
il void clear() {
while (!q.empty())
cur[q.front()] = 0, q.pop();
tot = 0;
}
array <array <pii, M>, M> isl;
array <vector <int>, N> suf, pre;
array <int, N> idx, dfn;
il void init(rg int n) {
for (rg int i = 1; i <= calc(n); i++) {
for (rg int j = i; j <= calc(n); j++) {
for (rg int k = (j - 1) * bsi + 1; k <= min(j * bsi, n); k++)
add(s[k], 1);
isl[i][j] = make_pair(tot, cur[tot]);
}
clear();
}
for (rg int i = 1; i <= n; i++)
suf[s[i]].push_back(i), dfn[i] = suf[s[i]].size() - 1;
for (rg int i = n; i >= 1; i--)
pre[s[i]].push_back(i), idx[i] = pre[s[i]].size() - 1;
}
il int query(rg int x, rg int y) {
if (abs(calc(x) - calc(y)) <= 1) {
for (rg int i = x; i <= y; i++)
add(s[i], 1);
rg int ans = cur[tot]; clear();
return ans;
}
rg int ans, tot; tie(tot, ans) = isl[calc(x) + 1][calc(y) - 1];
for (rg int i = x; i <= calc(x) * bsi; i++) {
while ((int)suf[s[i]].size() > ans + dfn[i] && suf[s[i]][ans + dfn[i]] <= y)
ans++, tot = s[i];
/* assert(ans + dfn[i] - 1 >= 0); */
/* if ((int)suf[s[i]].size() > ans + dfn[i] - 1 && suf[s[i]][ans + dfn[i] - 1] <= y) */
/* tot = min(tot, s[i]); */
}
for (rg int i = (calc(y) - 1) * bsi + 1; i <= y; i++) {
while ((int)pre[s[i]].size() > ans + idx[i] && pre[s[i]][ans + idx[i]] >= x)
ans++, tot = s[i];
/* assert(ans + idx[i] - 1 >= 0); */
/* if ((int)pre[s[i]].size() > ans + idx[i] - 1 && pre[s[i]][ans + idx[i] - 1] >= x) */
/* tot = min(tot, s[i]); */
}
/* write(ans), puts("@"); */
return ans;
}
}
signed main() {
/* freopen("P4168_2.in", "r", stdin); */
rg int n = read(), m = read();
for (rg int i = 1; i <= n; i++)
s[i] = h[i] = read();
/* sort(h.begin() + 1, h.begin() + 1 + n); */
/* rg int k = unique(h.begin() + 1, h.begin() + 1 + n) - h.begin() - 1; */
/* for (rg int i = 1; i <= n; i++) */
/* s[i] = lower_bound(h.begin() + 1, h.begin() + 1 + k, s[i]) - h.begin(); */
rg int lst = 0;
Blk::init(n);
while (m--) {
rg int l = read(), r = read();
l = (l ^ lst), r = (r ^ lst);
/* l = (l + lst - 1) % n + 1, r = (r + lst - 1) % n + 1; */
if (l > r) swap(l, r);
write(lst = Blk::query(l, r)), puts("");
}
return 0;
}