【思想】 分块思想的核心是将一个集合划分成若干个规模较小的子集。即让连续的序列组成一个块，便于进行处理。
为了便于处理，分块需要满足：
(1) 若子集规模很小， 对每个子集可使用关于子集规模的复杂度较高的算法。
(2) 若子集数目很少， 可以使用与整个集合规模有关的算法分别处理每个子集。
可以发现前两条性质其实是相互矛盾的， 因此为了均衡， 我们既不能让子集规模过大，
也不能让子集数目过大， 通常分块的大小都取n^0.5(根号n)。
通过预处理每一个分块，对于询问的区间，我们可以把其分为完全处于块中的区间与不完全处于块中的区间。完全处于块中的区间可以用预处理的结果得出答案，不完全处于块中的区间采用暴力枚举的方法。由于每个块的大小有限，所以枚举的时间复制度并不大。这样，算法的时间复杂度是O(n^0.5 * n)。
【优点】 分块算法的时间复杂度比一些数据结构的O(n logn)还大，那分块算法有什么用呢。但是，有些数据是普通的数据结构不能合并的，比如BZOJ2724: [Violet 6]蒲公英。
题目大意是给定 n 个数， 每次询问区间[L, R]内的众数， 强制在线。
很明显，这题是用线段树不能解决的。分块算法则能很好的完成。
在此题中我们就预处理出两个量： cnt[i][j]表示i 这个元素在前 j 块中的出现次数，以及 ans[i][j] 表示第i 块到第 j 块这个区间的众数。这两个量都是能在 O(n^0.5)的时间内预处理出来的。 cnt[i][j]较为简单就不赘述； 求 ans[i][j] 时我们先枚举并固定 i ， 当 i 确定后我们用一个数组来记录每个数字的出现次数， 初始时所有数字出现次数均为 0。 接着我们从第i 块左端点开始， 枚举之后的所有元素， 并更新出现次数的数组， 在这个程中我们是能求出当前众数的。 当枚举到的元素是某个块 j 的右端点时， 我们就知道 ans[i][j] 的值了， 不难发现这个做法复杂度是 O(n^0.5)的。
而对于询问，先找出完全被包含的分块，此时，答案要么是这些分块的众数，要么是不完全被包含的分块中的数。我们可以暴力将它们全部枚举一遍， 记录下它们当前的出现次数， 配合之前预处理的 cnt[i][ j]， 我们可以快速的算出一个数在第 L 块到第 R 块间的出现次数， 加上它在那 O( n^0.5) 个单个元素中出现的次数， 就是它在询问区间内出现的总次数， 进而我们可以利用它来更新答案。
代码如下：
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
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
const int N = 4 * 1e4 + 10, M = 2 * 1e2 + 5;
struct io {
io() {
freopen("dandelion.in", "r", stdin);
freopen("dandelion.out", "w", stdout);
}
~io() {
fclose(stdin);
fclose(stdout);
}
}z;
int Read() {
int val = 0, opt = 1;
char ch;
while (!(isdigit( ch = getchar() ) || ch == '-'));
if (ch == '-') opt = -1;
else val = ch - '0';
while (isdigit(ch = getchar())) (val *= 10) += ch - '0';
return val * opt;
}
int cnt[N][M], Ans[M][M], a[N], b[N], n, T, num, ti[N], End[M], s, L, p[N][M];
int wz(int i) {
return (i - 1) / s + 1;
}
void Find_cnt() {
for (int i = 1;i <= n; i++) p[a[i]][wz(i)]++;
for (int i = 1;i <= n; i++)
for (int j = 1;j <= L; j++)
cnt[a[i]][j] = cnt[a[i]][j - 1] + p[a[i]][j];
}
int conut(int li, int ri, int Num) {
return cnt[Num][ri] - cnt[Num][li - 1];
}
void Find_Ans() {
int t1, t2;
for (int i = 1;i <= L; i++) {
memset(ti, 0, sizeof ti);
for (int j = End[i - 1] + 1;j <= n; j++) {
if (!Ans[i][wz(j)]) Ans[i][wz(j)] = Ans[i][wz(j) - 1];
t1 = conut(i, wz(j), a[j]);
t2 = conut(i, wz(j), Ans[i][wz(j)]);
if ((t1 > t2) || (t1 == t2 && a[j] < Ans[i][wz(j)]))
Ans[i][wz(j)] = a[j];
}
}
}
int Que(int last) {
long long l, r, lc, rc, ans, t1, t2;
l = (Read() + last - 1) % n + 1, r = (Read() + last - 1) % n + 1;
if (l > r) swap(l, r);
lc = wz(l) + 1;
rc = wz(r) - 1;
ans = Ans[lc][rc];
memset(ti, 0, sizeof ti);
if (wz(l) == wz(r)) {
ans = 0;
for (int i = l;i <= r; i++) {
ti[a[i]]++;
if (ti[a[i]] > ti[ans] || (ti[a[i]] == ti[ans] && ans > a[i])) ans = a[i];
}
return b[ans];
}
for (int i = l;i <= End[lc - 1]; ++i) {
++ti[a[i]];
t1 = ti[a[i]] + cnt[a[i]][rc] - cnt[a[i]][lc - 1];
t2 = ti[ans] + cnt[ans][rc] - cnt[ans][lc - 1];
if (t1 > t2 || (t1 == t2 && ans > a[i])) ans = a[i];
}
for (int i = End[rc] + 1;i <= r; ++i) {
++ti[a[i]];
t1 = ti[a[i]] + cnt[a[i]][rc] - cnt[a[i]][lc - 1];
t2 = ti[ans] + cnt[ans][rc] - cnt[ans][lc - 1];
if (t1 > t2 || (t1 == t2 && ans > a[i])) ans = a[i];
}
return b[ans];
}
int main(void) {
n = Read(), T = Read();
for (int i = 1;i <= n; ++i) a[i] = b[i] = Read();
sort(b + 1, b + 1 + n);
num = unique(b + 1, b + 1 + n) - b - 1;
for (int i = 1;i <= n; i++) a[i] = lower_bound(b + 1, b + 1 + num, a[i]) - b;
s = (int)sqrt(n), L = n / s;
for (int i = 1;i <= L; ++i) End[i] = i * s;
if (n % s) End[++L] = n;
Find_cnt();
Find_Ans();
int mmp = 0;
while (T--)
printf("%d\n", mmp = Que(mmp));
return 0;
}
这里附上另一题代码：BZOJ1878: [SDOI2009]HH的项链
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
94
95
96
97
98
99
#include<algorithm>
#include<cstring>
#include<cmath>
#include<cstdio>
using namespace std;
const int N = 5 * 1e4 + 10, M = 230;
struct io {
io() {
freopen("HH.in","r",stdin);
freopen("HH.out","w",stdout);
}
~io() {
fclose(stdin);
fclose(stdout);
}
}zdx;
int Read() {
int val = 0, opt = 1;
char ch;
while (!(isdigit( ch = getchar() ) || ch == '-'));
if (ch == '-') opt = -1;
else val = ch - '0';
while (isdigit( ch = getchar() )) (val *= 10) += ch - '0';
return val * opt;
}
int cnt[N][M], p[N][M], Ans[N][M], a[N], b[N], End[M], n, num, s, L, co[N];
int wz(int x) {
return (x - 1) / s + 1;
}
void Find_cnt() {
for (int i = 1;i <= n; i++)
++p[a[i]][wz(i)];
for (int i = 1;i <= num; i++)
for (int j = 1;j <= L; j++)
cnt[i][j] = cnt[i][j - 1] + p[i][j];
}
void Find_Ans() {
for (int i = 1;i <= L; i++) {
memset(co, 0, sizeof co);
for (int j = End[i - 1] + 1;j <= n; j++) {
if (!(j % s - 1)) Ans[i][wz(j)] = Ans[i][wz(j) - 1];
if (!co[a[j]]) ++Ans[i][wz(j)];
++co[a[j]];
}
}
}
int work() {
int l = Read(), r = Read(), lc, rc, ans = 0;
lc = wz(l) + 1;
rc = wz(r) - 1;
memset(co, 0, sizeof co);
if (wz(l) == wz(r)) {
for (int i = l;i <= r; i++) {
ans += !co[a[i]];
++co[a[i]];
}
return ans;
}
ans = Ans[lc][rc];
for (int i = l;i <= End[lc - 1]; i++) {
ans += !(co[a[i]] + cnt[a[i]][rc] - cnt[a[i]][lc - 1]);
++co[a[i]];
}
for (int i = End[rc] + 1;i <= r; i++) {
ans += !(co[a[i]] + cnt[a[i]][rc] - cnt[a[i]][lc - 1]);
++co[a[i]];
}
return ans;
}
int main(void)
{
n = Read();
for (int i = 1;i <= n; i++) a[i] = b[i] = Read();
sort(b + 1, b + 1 + n);
num = unique(b + 1, b + 1 + n) - b -1;
for (int i = 1;i <= n; i++) a[i] = lower_bound(b + 1, b + 1 + num, a[i]) - b;
s = (int)sqrt(n);
L = n / s;
for (int i = 1;i <= L; i++) End[i] = i * s;
if (n % s) End[++L] = n;
Find_cnt();
Find_Ans();
int T = Read();
while (T--)
printf("%d\n", work());
return 0;
}