这道黑题为什么那么水 QAQ
这道题在 BZOJ 上为什么又又又又又是权限题

本题求区间众数,强制在线。

对于每次查询,必定可以分为整块的和非整块的,我们先预处理出第 $i$ 块到第 $j$ 块的众数( $max[i][j]$ )和某个数 $i$ 在前 $j$ 个块内的前缀和( $sum[i][j]$ )。对于非整块的部分 $O(\sqrt n)$ 暴力加到桶里,加上整块中的个数判断能否更新答案。然后判断 $l$ 与 $r$ 之间的块的众数是否能否更新答案。

预处理的话 $max$ 和 $sum$ 数组全都暴力扫一遍更新,时间复杂度 $O(n \sqrt n)$,详见代码。

时间复杂度:$O(n \sqrt n + m \sqrt m)$

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
// ==============================
// author: memset0
// website: https://memset0.cn
// ==============================
#include <bits/stdc++.h>
#define ll long long
#define rep(i,l,r) for (int i = l; i <= r; i++)

int read() {
int x = 0; bool m = 0; char c = getchar();
while (!isdigit(c) && c != '-') c = getchar();
if (c == '-') m = 1, c = getchar();
while (isdigit(c)) x = x * 10 + c - '0', c = getchar();
if (m) return -x; else return x;
}

const int maxn = 40010, maxm = 210;

int n, m, l, r, bl, br, tn, sqn, ans, now;
int a[maxn], b[maxn], bln[maxn], fst[maxm], tmp[maxn];
int cnt[maxn][maxm], sum[maxn][maxm], max[maxm][maxm];

bool better(int x, int y, int a, int b) {
return (x > y) || (x == y && a < b);
}

int query(int l, int r) {
ans = 0;
if (bln[l] == bln[r]) {
for (int i = l; i <= r; i++)
if (better(++tmp[a[i]], tmp[ans], a[i], ans))
ans = a[i];
for (int i = l; i <= r; i++)
--tmp[a[i]];
} else {
br = bln[r] - 1, bl = bln[l];
for (int i = l; i < fst[bln[l] + 1]; i++)
if (better(++tmp[a[i]] + sum[a[i]][br] - sum[a[i]][bl], tmp[ans] + sum[ans][br] - sum[ans][bl], a[i], ans))
ans = a[i];
for (int i = fst[bln[r]]; i <= r; i++)
if (better(++tmp[a[i]] + sum[a[i]][br] - sum[a[i]][bl], tmp[ans] + sum[ans][br] - sum[ans][bl], a[i], ans))
ans = a[i];
if (better(tmp[max[bl + 1][br]] + sum[max[bl + 1][br]][br] - sum[max[bl + 1][br]][bl], tmp[ans] + sum[ans][br] - sum[ans][bl], max[bl + 1][br], ans))
ans = max[bl + 1][br];
for (int i = l; i < fst[bln[l] + 1]; i++)
--tmp[a[i]];
for (int i = fst[bln[r]]; i <= r; i++)
--tmp[a[i]];
}
return ans;
}

int main() {

n = read(), m = read();
for (int i = 1; i <= n; i++)
b[i] = a[i] = read();
std::sort(b + 1, b + n + 1);
tn = std::unique(b + 1, b + n + 1) - b - 1;
for (int i = 1; i <= n; i++)
a[i] = std::lower_bound(b + 1, b + tn + 1, a[i]) - b;

sqn = sqrt(n) + 1;
if (sqn * sqn < n) sqn++;
bln[sqn + 1] = n + 1;
for (int i = 1; i <= n; i++) {
bln[i] = (i - 1) / sqn + 1;
if (!fst[bln[i]]) fst[bln[i]] = i;
}
for (int i = 1; i <= n; i++)
cnt[a[i]][bln[i]]++;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= sqn; j++)
sum[i][j] = sum[i][j - 1] + cnt[i][j];
for (int i = 1; i <= sqn; i++) {
memset(tmp, 0, sizeof(tmp)), now = 0;
for (int j = i; j <= sqn; j++) {
for (int k = fst[j]; k < fst[j + 1]; k++)
if (better(++tmp[a[k]], tmp[now], a[k], now))
now = a[k];
max[i][j] = now;
}
}

for (int i = 1; i <= m; i++) {
l = (read() + ans - 1) % n + 1;
r = (read() + ans - 1) % n + 1;
if (l > r) std::swap(l, r);
printf("%d\n", ans = b[query(l, r)]);
}

return 0;
}