众所周知，分块是一种比较暴力的数据结构。
虽说分块效率不高，但它能处理一些树状数组和线段树难以维护的东西（尤其是不具备可拆分性和可合并性的东西）。
分块遵循整块维护，块内暴力的原则。所以我们一般先考虑一个暴力算法，再使用分块优化。
建立分块：
我们定义一个分块的结构体 b，分别存储每个块的首尾。
对于每个块的第一个元素的下标，我们将其设为上一个块的最后一个元素的下标加 \(1\)。对于每个块的最后一个元素的下标，就是这个块的左端点加上一个块长再减 \(1\)。
因为可能会出现 \(n\) 不是块长或块的个数的倍数的情况，所以我们强制令最后一个块的末尾为序列长度 \(n\)。
最后，我们还要标记每个下标属于的块的编号。这非常有用，所有分块题都需要。
我们一般将块的个数和块长设为 \(\lfloor \sqrt{n}\rfloor\)（为什么下文会提到）。
带修莫队：那我走？（雾）
//一般来说所有分块题都要维护左右端点，当然有的题目还要维护额外的信息
struct blocks{
int l,r;//块的左右端点
} b[SqrtN];
int belong[N];//belong[i]表示下标i属于的块的编号
int block_cnt,block_len;//块的个数，块长
void build_block(){
block_cnt = block_len = (int)sqrt(n);
for(int i = 1;i <= block_cnt;i++){
b[i].l = b[i - 1].r + 1;
b[i].r = b[i].l + block_len - 1;
}
b[block_cnt].r = n;//上文讲了的
for(int i = 1;i <= block_cnt;i++)
for(int j = b[i].l;j <= b[i].r;j++)
belong[j] = i;
}
区间查询：
引入中说，分块遵循整体维护，块内暴力的原则。
所以分块查询一般套路如下：
如果查询两端点在同一块内，直接暴力，复杂度 \(O(s)\)，\(s\) 为块长。
否则，我们把询问拆分成三部分：
首先是两个散块，即左端点到左端点所在块的末尾，以及右端点所在块的开头到右端点两段，这两段也是暴力,复杂度也是 \(O(s)\)。
其次是中间的整块（也可能没有），对于这些部分，我们需要对它们维护一些信息，这样就可以降低整块查询的复杂度（至多不能超过 \(O(s)\)），否则，分块算法就会退化成原版的暴力。
假定单整块查询的复杂度是 \(O(1)\)，那么多个整块查询的复杂度是 \(O(\frac{n}{s})\)，即跟块的数量同级。所以整个查询时间复杂度为 \(O(s + \frac{n}{s})\)
在建立分块中说了，一般将块的个数和块长设为 \(\lfloor \sqrt{n}\rfloor\)。由均值不等式，\(O(s + \frac{n}{s})\) 在 \(s = \sqrt{n}\) 时，取到最小值 \(O(\sqrt{n})\)（均值不等式不用我说了吧）。
拿到一道分块题，我们可以先取块长 \(s = \lfloor \sqrt{n} \rfloor\)，发现有更优解再调整块长。
例题1：教主的魔法
非常经典的带修分块题。
查询一个区间有多少个大于 \(C\) 的数其实很难用线段树或树状数组维护（树套树还是可以的），但本题的修改是区间加，这样树套树差不多也萎了，所以考虑分块。
还是一样先设块长和块的个数为 \(\lfloor \sqrt{n} \rfloor\)，建好分块。
先考虑暴力解法。很容易想到用一个临时数组，复制下要查询的区间 \([l,r]\)，对这个数组排序再二分。
这样的暴力算法单次复杂度修改 \(O(n)\)，查询 \(O(n \log n)\)，显然过不了。
因此，我们考虑分块，接下来分别优化修改和查询。
学过线段树的肯定知道“懒标记”这个东西，懒标记用到分块上同样适用。
还记得分块的整块维护，块内暴力的原则吗？修改也是一样的。
和查询类似，当左右端点在同一块内时，直接暴力修改，复杂度 \(O(\sqrt{n})\)。
否则，分别暴力修改左端点 \(l\) 到左端点 \(l\) 所在块的右边界和右端点 \(r\) 所在块的右边界到右端点 \(r\)，复杂度 \(O(\sqrt{n})\)。
对于每个整块，将这些整块的标记都加上 \(W\)，代表这些整块的数都要加上 \(W\)，复杂度 \(O(\sqrt{n})\)。
那么查询呢？
按照暴力的思路，我们应该对每个块内排序再二分。所以我们可以先预处理，对每个块内排序。但是每次要修改怎么办呢？
我们可以发现：对于一个单调递增的序列，整体加一个数是不会改变其单调性的，所以对于整块，只用打标记即可。
对于两个散块，暴力加后直接复制到临时数组上排序，复杂度 \(O(\sqrt{n} \log \sqrt{n})\)。
这样查询就简单了，在每个块内二分查找即可。
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e6 + 9,SqrtN = 1e3 + 9;
int n,q;
int a[N],tmp[N];
struct blocks{
int l,r,add;//额外维护一个标记
} b[SqrtN];
int belong[N];//belong[i]表示下标i属于的块的编号
int block_cnt,block_len;
void block_sort(int block_id){
int l = b[block_id].l,r = b[block_id].r;
for(int i = l;i <= r;i++)
tmp[i] = a[i];
sort(tmp + l,tmp + r + 1);
}
void build_block(){
block_cnt = block_len = (int)sqrt(n);
for(int i = 1;i <= block_cnt;i++){
b[i].l = b[i - 1].r + 1;
b[i].r = b[i].l + block_len - 1;
}
b[block_cnt].r = n;
for(int i = 1;i <= block_cnt;i++){
block_sort(i);//块内排序
for(int j = b[i].l;j <= b[i].r;j++)
belong[j] = i;
}
}
void update(int l,int r,int k){
int pos_l = belong[l],pos_r = belong[r];
if(pos_l == pos_r){
for(int i = l;i <= r;i++)
a[i] += k;
block_sort(pos_r);
return;
}
for(int i = l;i <= b[pos_l].r;i++)
a[i] += k;
for(int i = b[pos_r].l;i <= r;i++)
a[i] += k;
for(int i = pos_l + 1;i <= pos_r - 1;i++)
b[i].add += k;
block_sort(pos_l);
block_sort(pos_r);
}
int query(int l,int r,int k){
int ret = 0;
int pos_l = belong[l],pos_r = belong[r];
if(pos_l == pos_r){
for(int i = l;i <= r;i++)
if(a[i] + b[pos_l].add >= k)
ret++;
return ret;
}
for(int i = l;i <= b[pos_l].r;i++)
if(a[i] + b[pos_l].add >= k)
ret++;
for(int i = b[pos_r].l;i <= r;i++)
if(a[i] + b[pos_r].add >= k)
ret++;
for(int i = pos_l + 1;i <= pos_r - 1;i++){
int L = b[i].l,R = b[i].r;
int pos = lower_bound(tmp + L,tmp + R + 1,k - b[i].add) - tmp;
ret += b[i].r - pos + 1;
}
return ret;
}
signed main(){
ios::sync_with_stdio(false);
cin >> n >> q;
for(int i = 1;i <= n;i++)
cin >> a[i];
build_block();
for(int i = 1;i <= q;i++){
string op;
int l,r,k;
cin >> op >> l >> r >> k;
if(op == "M")
update(l,r,k);
else
cout << query(l,r,k) << '\n';
}
return 0;
}
同样，对于一些静态问题，分块也能很好地维护。
例题2：[Violet] 蒲公英
本题大意就是求一个区间出现最多的数（众数），如有多个则取最小的一个，强制在线。
显然，区间众数不满足可合并性或可拆分性，所以分块就成了一个很好的选择。
先取块长为 \(O(\sqrt{n})\)，然后我们考虑什么样的数可能成为区间众数。
凭借敏锐的观察力（雾），发现区间众数只可能是这两种数：
-
整块中的众数（最小的一个）。
-
散块中出现了的数。
显然，如果一个数只在散块中出现过，且出现次数不多于整块众数，那么不管怎么样，整块的众数肯定更优。这样就将需要比较的数压缩到了 \(O(\sqrt{n})\) 级别。
另外，众数只与值出现的次数有关，与值本身无关（在本题中与大小关系有关），所以考虑离散化把值域压缩至 \(O(n)\) 级别。
因为是静态问题，所以我们预处理两个数组：
-
s[SqrtN][N]：s[i][j]表示前 \(i\) 个块中数 \(j\) 出现的次数。 -
p[SqrtN][SqrtN]：p[i][j]代表第 \(i \sim j\) 个块中的众数。
那怎么预处理呢？
对于 s 数组，两重循环。外层循环枚举块的编号 \(i\)，内层循环枚举第 \(i\) 个块内的元素 \(a_j\)，每扫过一个，就将 s[i][a[j]] 加 \(1\)。另外，我们还好把前 \(i - 1\) 个块的元素转移过来。用一层循环，枚举值 \(j \leq n\)（毕竟离散化了），将 s[i][j] 加 s[i - 1][j]。
外层循环复杂度 \(O(\sqrt{n})\)，内层循环复杂度 \(O(n)\)（瓶颈在转移上），所以预处理 s 数组的复杂度为 \(O(n\sqrt{n})\)。
对于 p 数组，我们用两层循环枚举左块 \(i\) 和右块 \(j\)。另外，我们还要维护一个计数器 cnt[N]，记录值出现的次数，以及 Max 和 Max_cnt 用于打擂台。
先考虑最暴力的方法：暴力扫描第 \(i \sim j\) 块中的所有数 \(a_k\)，每扫到一个立刻将 cnt[a[k]] 加 \(1\)，同时立刻将 \(a_k\) 和 Max 打擂台。
但这样最内层循环的复杂度是 \(O(n)\) 的，所以这种预处理 p 数组的方法复杂度 \(O(n ^ 2)\)，需要优化。
问：我们每次真的需要清空计数器再重新全部扫描吗？
答：显然是不需要的。
我们发现：当我们扫描完第 \(i \sim j - 1\) 块时，其实可以通过对第 \(j\) 块的扫描配合此时的计数器就可以得到扫完第 \(i \sim j\) 块时的计数器，完全不需要清空，因此内层循环只用扫第 \(j\) 个块即可，复杂度 \(O(\sqrt{n})\)。
不过，当最外层循环的 \(i\) 加 \(1\) 时，这就得把计数器清空了，但复杂度还是优化到了 \(O(n \sqrt{n})\)，可以接受。
预处理完后，就可以查询了。还记得可能成为众数的数吗？这里在放出来：
-
整块中的众数（最小的一个）。
-
散块中出现了的数。
如果区间左右端点在同一个块中，直接按照预处理 p 数组的方式暴力即可，复杂度 \(O(\sqrt{n})\)。
首先，我们必须得得到整块中的众数及其在整个区间中出现的次数。
记左端点所在块的编号为 pos_l，右端点所在块的编号为 pos_r，显然，整块中的区间众数就是 p[pos_l + 1][pos_r - 1]。设其为 ret，则 ret 在整块中的出现次数 ret_cnt 即为 s[pos_r - 1][ret] - s[pos_l][ret]。
我们两次扫描两个散块，当扫描到的数 \(a_k = ret\) 时，将 ret_cnt 加 \(1\)，就得到了整块中的众数在整个区间的出现次数。
散块中的数处理和预处理 p 数组是类似的，不过打擂台的方式不同：因为我们只扫描散块，没考虑整块，所以每次打擂台比较的是 Max_cnt 和 cnt[a[k]] + s[pos_r - 1][a[k]] - s[pos_l][a[k]]。
这样得到的查询算法单次复杂度 \(O(\sqrt{n})\)。需要说明的是：每次清空 cnt 如果使用的是 memset，因为本题数据宽松，加上 memset 常数小，可以通过本题，但更优的方法是先扫描散块，只清空散块中出现的数，复杂度 \(O(\sqrt{n})\)。
这样，本题的时间复杂度为 \(O((n + m)\sqrt{n})\)，空间复杂度 \(O(n \sqrt{n})\)（瓶颈在 s 数组上）。
#include<bits/stdc++.h>
using namespace std;
const int N = 4e4 + 9,SqrtN = 2e2 + 9;
int n,m,ans;
int a[N],tmp[N],len;
int block_cnt,block_len;
struct block{
int l,r;
} b[SqrtN];
int belong[N];
int p[SqrtN][SqrtN];
int s[SqrtN][N];
void build_block(){
block_cnt = block_len = (int)sqrt(n);
for(int i = 1;i <= block_cnt;i++){
b[i].l = b[i - 1].r + 1;
b[i].r = b[i].l + block_len - 1;
}
b[block_cnt].r = n;
for(int i = 1;i <= block_cnt;i++)
for(int j = b[i].l;j <= b[i].r;j++)
belong[j] = i;
}
int cnt[N];
void init(){
for(int i = 1;i <= block_cnt;i++){
for(int j = 1;j <= len;j++)
s[i][j] = s[i - 1][j];
for(int j = b[i].l;j <= b[i].r;j++)
s[i][a[j]]++;
}
for(int i = 1;i <= block_cnt;i++){
int Max = INT_MAX,Max_cnt = 0;
memset(cnt,0,sizeof cnt);
for(int j = i;j <= block_cnt;j++){
for(int k = b[j].l;k <= b[j].r;k++){
cnt[a[k]]++;
if(cnt[a[k]] > Max_cnt || (cnt[a[k]] == Max_cnt && a[k] < Max)){
Max = a[k];
Max_cnt = cnt[a[k]];
}
}
p[i][j] = Max;
}
}
}
int query(int l,int r){
int pos_l = belong[l],pos_r = belong[r];
int Max = INT_MAX,Max_cnt = 0;
memset(cnt,0,sizeof cnt);
int ret = p[pos_l + 1][pos_r - 1],ret_cnt = s[pos_r - 1][ret] - s[pos_l][ret];
if(pos_l == pos_r){
for(int i = l;i <= r;i++){
cnt[a[i]]++;
if(cnt[a[i]] > Max_cnt || (cnt[a[i]] == Max_cnt && a[i] < Max)){
Max = a[i];
Max_cnt = cnt[a[i]];
}
}
return Max;
}
for(int i = l;i <= b[pos_l].r;i++)
cnt[a[i]]++;
for(int i = b[pos_r].l;i <= r;i++)
cnt[a[i]]++;
ret_cnt += cnt[ret];
for(int i = l;i <= b[pos_l].r;i++){
int val = cnt[a[i]] + s[pos_r - 1][a[i]] - s[pos_l][a[i]];
if(val > Max_cnt || (val == Max_cnt && a[i] < Max)){
Max = a[i];
Max_cnt = val;
}
}
for(int i = b[pos_r].l;i <= r;i++){
int val = cnt[a[i]] + s[pos_r - 1][a[i]] - s[pos_l][a[i]];
if(val > Max_cnt || (val == Max_cnt && a[i] < Max)){
Max = a[i];
Max_cnt = val;
}
}
if(Max_cnt > ret_cnt || (Max_cnt == ret_cnt && Max < ret))
ret = Max;
return ret;
}
int main(){
scanf("%d%d", &n, &m);
for(int i = 1;i <= n;i++){
scanf("%d", &a[i]);
tmp[i] = a[i];
}
sort(tmp + 1,tmp + n + 1);
len = unique(tmp + 1,tmp + n + 1) - tmp - 1;
for(int i = 1;i <= n;i++)
a[i] = lower_bound(tmp + 1,tmp + len + 1,a[i]) - tmp;
build();
init();
for(int i = 1;i <= m;i++){
int l,r;
scanf("%d%d", &l, &r);
l = (l + ans - 1) % n + 1;
r = (r + ans - 1) % n + 1;
if(l > r)
swap(l,r);
ans = tmp[query(l,r)];
printf("%d\n",ans);
}
}
本题是在线的，那么如果本题如果支持离线，还有别的做法吗？这就要隆重请出莫队了。
莫队：
未完待续（逃）。