Bzoj 2724(分块)

BZOJ 2724
题意:强制在线不修改求区间众数。
如果不强制在线,可以离线莫队直接处理。
这里强制在线,我们将原数列分块,预处理$i$块到$j$块区间的众数,直接开桶统计,用于求解整块的区间。
用vector把相同的数的位置按顺序存储下来,求众数可以用询问区间的每个数字去求他出现次数,比较即可。
对于整块,我们预处理了$i$块到$j$块区间的众数,直接询问这个数字在询问区间出现次数即可;
对于不完整的块,我们暴力每个数字在询问区间出现次数即可
最后输出即可,时间复杂度$O(m \cdot logn+\frac nm)$, 其中$n$为数列长,$m$为每个块长,根据均值不等式,在$m \cdot logn=\frac nm$时和有最小值,$m=\sqrt{\frac{n}{logn}}$,即得到最优分块大小

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
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<cmath>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
using namespace std;
const int MAXN = 40000 + 5;
int n, q, whw, ai[MAXN], key = 0, tax[MAXN], tax1[MAXN], blolen, bl[MAXN], s[1005][1005];
vector<int> hh[MAXN];
int cx(int v, int x, int y) {
return upper_bound(hh[v].begin(), hh[v].end(), y) - upper_bound(hh[v].begin(), hh[v].end(), x - 1);
}
int query(int x, int y) {
int mks = cx(s[bl[x] + 1][bl[y] - 1], x, y), ret = s[bl[x] + 1][bl[y] - 1];
for (int i = x; i <= min(y, bl[x] * blolen); i++) {
int tmp = cx(ai[i], x, y);
if (tmp > mks) ret = ai[i], mks = tmp; else if (tmp == mks && ai[i] < ret) ret = ai[i];
}
if (bl[x] != bl[y]) for (int i = (bl[y] - 1) * blolen + 1; i <= y; i++) {
int tmp = cx(ai[i], x, y);
if (tmp > mks) ret = ai[i], mks = tmp; else if (tmp == mks && ai[i] < ret) ret = ai[i];
}
return ret;
}
void clean() {}
int solve() {
clean();
blolen = (int)sqrt((db)n / log2(n));
for (int i = 1; i <= n; i++) scanf("%d", &ai[i]), tax1[i] = ai[i], bl[i] = (i - 1) / blolen + 1;
sort(tax1 + 1, tax1 + 1 + n), whw = unique(tax1 + 1, tax1 + 1 + n) - tax1 - 1;
for (int i = 1; i <= n; i++) ai[i] = lower_bound(tax1 + 1, tax1 + 1 + whw, ai[i]) - tax1, hh[ai[i]].push_back(i);
bool f = n % blolen;
for (int i = 1; i <= n / blolen + f; i++) {
ms(tax, 0); int mks = 0;
for (int j = i; j <= n / blolen + f; j++) {
s[i][j] = s[i][j - 1];
for (int k = (j - 1) * blolen + 1; k <= min(n, j * blolen); k++) {
tax[ai[k]]++;
if (tax[ai[k]] > mks) mks = tax[ai[k]], s[i][j] = ai[k]; else if (tax[ai[k]] == mks && ai[k] < s[i][j]) s[i][j] = ai[k];
}
}
}
while (q--) {
int l, r;
scanf("%d%d", &l, &r);
l = (l + key - 1) % n + 1, r = (r + key - 1) % n + 1;
if (l > r) swap(l, r);
printf("%d\n", key = tax1[query(l, r)]);
}
return 0;
}
int main() {
scanf("%d%d", &n, &q), solve();
return 0;
}
------ 本文结束 ------