我也不知道为什么一个大二的ACM选手没学分块。
我怎么记得大一的时候，学长教给我的分块就只有 block 和 num 两个变量来着...好吧，应该是我没认真学。正好前两天朋友给学弟开课，乘机去蹭了一节课。然后...我还是不会哇，菜的一逼塌糊涂。
还是 卿学姐 好哇，多听几遍，睡得贼香。
分块嘛，其实就是优雅的暴力，和莫队（不会）有点异曲同工的赶脚。通过将数组分成小块以降低复杂度。
通常情况下：
每个块的大小（block）为 \(\sqrt{n}\)块数（num）为 \(\sqrt{n}\)或\(\sqrt{n}+1\)每个块的左端点（L[x]）为 \((i-1)*block+1\)每个块的右端点（R[x]）为 \(i*block\)（最后一块右端点为\(n\)）位置 x 上的数属于（belong[x]）第 \((i-1)/block+1\) 块每次修改或查询的时候如果需要维护 [L, R] 的数，如果L、R被分在了同一块，那么就直接暴力跑就行了，反正复杂度不会超过\(\sqrt{n}\)。
如果不在一块，那就先暴力更新所有和 L 同一块且位置在 L 之后的数，再更新所有和 R 在同一块且位置在 R 之前的数，最后，再去把这中间的若干块直接按“块”更新（利用新数组之类的）。这样的复杂度也只有 \(\sqrt{n}\)量级。从而完成多次优雅的在线更新和查询。
没啥好些的，就按照上边写的来就行。因为是纯板子题，所以还是放个代码好了。
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int maxn = 5e4 + 5; int belong[maxn]; int block, num; int l[maxn], r[maxn]; int n; int a[maxn]; int more[maxn]; void build() { block = sqrt(n); num = n / block; if (n % block != 0) { num++; } for (int i = 1; i <= num; i++) { l[i] = (i - 1) * block + 1; r[i] = i * block; } r[num] = n; for (int i = 1; i <= n; i++) { belong[i] = (i - 1) / block + 1; } } void update(int l, int r, int c) { if (belong[l] == belong[r]) { for (int i = l; i <= r; i++) { a[i] += c; } return; } for (int i = l; belong[i] == belong[l]; i++) { a[i] += c; } for (int i = r; belong[i] == belong[r]; i--) { a[i] += c; } for (int i = belong[l] + 1; i <= belong[r] - 1; i++) { more[i] += c; } } int query(int x) { return a[x] + more[belong[x]]; } int main() { while (~scanf("%d", &n)) { memset(more, 0, sizeof(more)); memset(belong, 0, sizeof(belong)); memset(a, 0, sizeof(a)); for (int i = 1; i <= n; i++) { scanf("%d", &a[i]); } build(); for (int i = 1; i <= n; i++) { int f, l, r, c; scanf("%d%d%d%d", &f, &l, &r, &c); if (f == 0) { update(l, r, c); } else { printf("%d\n", query(r)); } } } return 0; }需要 vector 数组进行区间排序，然后 lower_bound 二分找答案就行了。
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int maxn = 5e4 + 5; int belong[maxn]; int block, num; int l[maxn], r[maxn]; int a[maxn]; int more[maxn]; vector<int> v[maxn]; int n; void build() { block = sqrt(n); num = n / block; if (n % block != 0) { num++; } for (int i = 1; i <= num; i++) { l[i] = (i - 1) * block + 1; r[i] = i * block; } r[num] = n; for (int i = 1; i <= n; i++) { belong[i] = (i - 1) / block + 1; v[belong[i]].push_back(a[i]); } for (int i = 1; i <= num; i++) { sort(v[i].begin(), v[i].end()); } } void pushup(int x) { v[x].clear(); for (int i = l[x]; i <= r[x]; i++) { v[x].push_back(a[i]); } sort(v[x].begin(), v[x].end()); } void update(int l, int r, int c) { if (belong[l] == belong[r]) { for (int i = l; i <= r; i++) { a[i] += c; } pushup(belong[l]); return; } for (int i = l; belong[i] == belong[l]; i++) { a[i] += c; } pushup(belong[l]); for (int i = r; belong[i] == belong[r]; i--) { a[i] += c; } pushup(belong[r]); for (int i = belong[l] + 1; i <= belong[r] - 1; i++) { more[i] += c; } } int query(int l, int r, int c) { int ans = 0; if (belong[l] == belong[r]) { for (int i = l; i <= r; i++) { if (a[i] + more[belong[i]] < c) { ans++; } } return ans; } for (int i = l; belong[i] == belong[l]; i++) { if (a[i] + more[belong[i]] < c) { ans++; } } for (int i = r; belong[i] == belong[r]; i--) { if (a[i] + more[belong[i]] < c) { ans++; } } for (int i = belong[l] + 1; i <= belong[r] - 1; i++) { int temp = c - more[i]; ans += lower_bound(v[i].begin(), v[i].end(), temp) - v[i].begin(); } return ans; } int main() { while (~scanf("%d", &n)) { memset(more, 0, sizeof(more)); memset(belong, 0, sizeof(belong)); for (int i = 1; i <= n; i++) { scanf("%d", &a[i]); } build(); for (int i = 1; i <= n; i++) { int f, l, r; int c; scanf("%d%d%d%d", &f, &l, &r, &c); if (f == 0) { update(l, r, c); } else { printf("%d\n", query(l, r, c * c)); } } } return 0; }几乎和第二题没差，就不上代码了。
几乎和第一题没差，需要维护每个块的和 s 数组，查询区间和。
这题相对前几题来说要难上不少，刚开始做的时候没反应过来，后来开方操作最多只会做64次，那么就肯定可以暴力了，不过需要标记整个块里是不是只有 0或1 （不需要开方操作了）。然后就是正常的区间加法，毕竟分块就是暴力哇。
#include <bits/stdc++.h> using namespace std; const int maxn = 5e4 + 5; int belong[maxn]; int L[maxn], R[maxn]; int a[maxn]; int n; int block, num; int s[maxn]; int mark[maxn]; // 标记 1 为区间中只有 0 或 1 void build() { block = sqrt(n); num = n / block; if (n % block) { num++; } for (int i = 1; i <= num; i++) { L[i] = (i - 1) * block + 1; R[i] = i * block; } R[num] = n; for (int i = 1; i <= n; i++) { belong[i] = (i - 1) / block + 1; s[belong[i]] += a[i]; } } void update(int l, int r) { if (belong[l] == belong[r]) { if (mark[belong[l]] == 0) { mark[belong[l]] = 1; for (int i = l; i <= r; i++) { s[belong[i]] -= a[i]; a[i] = sqrt(a[i]); s[belong[i]] += a[i]; } for (int i = L[belong[l]]; i <= R[belong[l]]; i++) { if (a[i] > 1) mark[belong[l]] = 0; } } return; } if (mark[belong[l]] == 0) { mark[belong[l]] = 1; for (int i = l; belong[i] == belong[l]; i++) { s[belong[i]] -= a[i]; a[i] = sqrt(a[i]); s[belong[i]] += a[i]; } for (int i = L[belong[l]]; i <= R[belong[l]]; i++) { if (a[i] > 1) mark[belong[l]] = 0; } } if (mark[belong[r]] == 0) { mark[belong[r]] = 1; for (int i = r; belong[i] == belong[r]; i--) { s[belong[i]] -= a[i]; a[i] = sqrt(a[i]); s[belong[i]] += a[i]; } for (int i = L[belong[r]]; i <= R[belong[r]]; i++) { if (a[i] > 1) mark[belong[r]] = 0; } } for (int i = belong[l] + 1; i <= belong[r] - 1; i++) { if (mark[i] == 1) continue; s[i] = 0; mark[i] = 1; for (int j = L[i]; j <= R[i]; j++) { a[j] = sqrt(a[j]); s[i] += a[j]; if (a[j] > 1) mark[i] = 0; } } } int query(int l, int r) { int ans = 0; if (belong[l] == belong[r]) { for (int i = l; i <= r; i++) { ans += a[i]; } return ans; } for (int i = l; belong[i] == belong[l]; i++) { ans += a[i]; } for (int i = r; belong[i] == belong[r]; i--) { ans += a[i]; } for (int i = belong[l] + 1; i <= belong[r] - 1; i++) { ans += s[i]; } return ans; } int main() { while (~scanf("%d", &n)) { memset(mark, 0, sizeof(mark)); memset(belong, 0, sizeof(belong)); memset(s, 0, sizeof(s)); memset(a, 0, sizeof(a)); for (int i = 1; i <= n; i++) { scanf("%d", &a[i]); } build(); for (int i = 1; i <= n; i++) { int f, l, r, c; scanf("%d%d%d%d", &f, &l, &r, &c); if (f == 0) { update(l, r); } else { printf("%d\n", query(l, r)); } } } return 0; }每次在 l 位置前插入 r 数值，其实这是个 rope 裸题，stl 天下第一。那既然这是个分块专题，就得用分块做。
这题的难点就是插入达到\(\sqrt{n}\)后进行重新分块，不然会超时（比如一直往这块里添加）。
#include <bits/stdc++.h> using namespace std; const int maxn = 1e5 + 5; int n; int belong[maxn]; int a[maxn]; int block, num; vector<int> v[maxn]; int temp[maxn << 2]; int cnt; void build() { block = sqrt(n); num = n / block; if (n % block) { num++; } for (int i = 1; i <= n; i++) { belong[i] = (i - 1) / block + 1; v[belong[i]].push_back(a[i]); } } void re_build() { cnt = 0; int tot = 0; for (int i = 1; i <= num; i++) { for (auto it = v[i].begin(); it != v[i].end(); it++) { temp[tot++] = *it; } v[i].clear(); } block = sqrt(tot); for (int i = 0; i < tot; i++) { v[(i - 1) / block + 1].push_back(temp[i]); } num = tot / block; if (tot % block) num++; } void query(int x, int &q, int &t) { for (int i = 1; i <= num; i++) { if (x > (int)v[i].size()) { x -= (int)v[i].size(); } else { q = i; t = x - 1; return; } } } void update(int l, int r) { cnt++; int q = -1, t = -1; query(l, q, t); v[q].insert(v[q].begin() + t, r); if (cnt == block) { re_build(); } return; } int main() { while (~scanf("%d", &n)) { cnt = 0; for (int i = 0; i <= n; i++) { v[i].clear(); } for (int i = 1; i <= n; i++) { scanf("%d", &a[i]); } build(); for (int i = 1; i <= n; i++) { int f, l, r, c; scanf("%d%d%d%d", &f, &l, &r, &c); if (f == 0) { update(l, r); } else { int q = -1, t = -1; query(r, q, t); printf("%d\n", v[q][t]); } } } return 0; }这题比较麻烦，但是不算难，就是写起来烦，需要多维护一个数组，乘法分配律就完事了。然后我 memset 赋 1 debug 了半小时...
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int mod = 10007; const int maxn = 1e5 + 5; int n; int block, num; ll a[maxn]; ll belong[maxn]; ll more[maxn]; ll s[maxn]; int L[maxn], R[maxn]; void build() { block = sqrt(n); num = n / block; if (n % block) { num++; } for (int i = 1; i <= num; i++) { L[i] = (i - 1) * block + 1; R[i] = i * block; } R[num] = n; for (int i = 1; i <= n; i++) { belong[i] = (i - 1) / block + 1; } } void pushup(int x) { for (int i = L[x]; i <= R[x]; i++) { a[i] = (a[i] * s[x] + more[x]) % mod; } s[x] = 1; more[x] = 0; } void update_add(int l, int r, ll c) { if (belong[l] == belong[r]) { pushup(belong[l]); for (int i = l; i <= r; i++) { a[i] = (a[i] + c) % mod; } return; } pushup(belong[l]); for (int i = l; belong[i] == belong[l]; i++) { a[i] = (a[i] + c) % mod; } pushup(belong[r]); for (int i = r; belong[i] == belong[r]; i--) { a[i] = (a[i] + c) % mod; } for (int i = belong[l] + 1; i <= belong[r] - 1; i++) { more[i] = (more[i] + c) % mod; } } void update_mul(int l, int r, ll c) { if (belong[l] == belong[r]) { pushup(belong[l]); for (int i = l; i <= r; i++) { a[i] = (a[i] * c) % mod; } return; } pushup(belong[l]); for (int i = l; belong[i] == belong[l]; i++) { a[i] = (a[i] * c) % mod; } pushup(belong[r]); for (int i = r; belong[i] == belong[r]; i--) { a[i] = (a[i] * c) % mod; } for (int i = belong[l] + 1; i <= belong[r] - 1; i++) { more[i] = (more[i] * c) % mod; s[i] = (s[i] * c) % mod; } } ll query(int x) { return a[x] * s[belong[x]] + more[belong[x]]; } int main() { while (~scanf("%d", &n)) { for (int i = 0; i <= n; i++) { s[i] = 1; } memset(more, 0, sizeof(more)); for (int i = 1; i <= n; i++) { scanf("%lld", &a[i]); } build(); for (int i = 1; i <= n; i++) { int f, l, r; ll c; scanf("%d%d%d%lld", &f, &l, &r, &c); if (f == 0) { update_add(l, r, c); } else if (f == 1) { update_mul(l, r, c); } else { printf("%lld\n", query(r) % mod); } } } return 0; }先查询 [l, r] 中有多少 c ，在把中间的数都改成 c 。多开一个 vis 数组，如果块中的所有数都并非都一样，则置 vis[x] = -1，此时需要强制暴力找；否则 vis 数组记录的就是整个块中的数是多少，满足条件就直接 ans += block 。
#include <bits/stdc++.h> using namespace std; const int maxn = 1e5 + 5; int belong[maxn]; int n, block, num; int a[maxn]; int L[maxn], R[maxn]; int vis[maxn]; void build() { block = sqrt(n); num = n / block; if (n % block) { num++; } for (int i = 1; i <= num; i++) { L[i] = (i - 1) * block + 1; R[i] = i * block; } R[num] = n; for (int i = 1; i <= n; i++) { belong[i] = (i - 1) / block + 1; } } void pushup(int x) { if (vis[x] == -1) return; for (int i = L[x]; i <= R[x]; i++) { a[i] = vis[x]; } vis[x] = -1; } int query(int l, int r, int c) { int ans = 0; if (belong[l] == belong[r]) { pushup(belong[l]); for (int i = l; i <= r; i++) { if (a[i] == c) { ans++; } a[i] = c; } return ans; } pushup(belong[l]); for (int i = l; belong[i] == belong[l]; i++) { if (a[i] == c) { ans++; } a[i] = c; } pushup(belong[r]); for (int i = r; belong[i] == belong[r]; i--) { if (a[i] == c) { ans++; } a[i] = c; } for (int i = belong[l] + 1; i <= belong[r] - 1; i++) { if (vis[i] == -1) { for (int j = L[i]; j <= R[i]; j++) { if (a[j] == c) { ans++; } } } else { if (vis[i] == c) { ans += block; } } vis[i] = c; } return ans; } int main() { while (~scanf("%d", &n)) { memset(belong, 0, sizeof(belong)); memset(vis, -1, sizeof(vis)); for (int i = 1; i <= n; i++) { scanf("%d", &a[i]); } build(); for (int i = 1; i <= n; i++) { int l, r, c; scanf("%d%d%d", &l, &r, &c); printf("%d\n", query(l, r, c)); } } return 0; }这题...就很麻烦了，需要先预处理出每个块内的众数，然后再用 upper_bound - lower_bound 去得到某个数的个数。总之说起来挺复杂的，看着代码理解一下还是可以的。
吐槽一下讨论版玄学，这啥数据啊，块的大小还得是 30 ，我代码都重构的不成样子了...
#include <bits/stdc++.h> using namespace std; const int maxn = 1e5 + 5; int n; int block, num; int belong[maxn]; int a[maxn]; map<int, int> mp; // a[i] 是第几个出现的 int val[maxn]; // val[id] = a[i] int mark[maxn / 30][maxn / 30]; // 预处理每个整块的众数 int cnt[maxn]; vector<int> v[maxn]; // 记录每个数出现的每一个位置 /*void build() { }*/ inline int get_id(int l, int r, int x) { return upper_bound(v[x].begin(), v[x].end(), r) - lower_bound(v[x].begin(), v[x].end(), l); } inline int query(int l, int r) { int MAX = 0, tot = 0; if (belong[l] == belong[r]) { for (int i = l; i <= r; i++) { int temp = get_id(l, r, a[i]); if (temp > tot || (temp == tot && val[a[i]] < val[MAX])) { tot = temp; MAX = a[i]; } } return MAX; } for (int i = l; belong[i] == belong[l]; i++) { int temp = get_id(l, r, a[i]); if (temp > tot || (temp == tot && val[a[i]] < val[MAX])) { tot = temp; MAX = a[i]; } } for (int i = r; belong[i] == belong[r]; i--) { int temp = get_id(l, r, a[i]); if (temp > tot || (temp == tot && val[a[i]] < val[MAX])) { tot = temp; MAX = a[i]; } } int res = mark[belong[l] + 1][belong[r] - 1]; int temp = get_id(l, r, res); if (temp > tot || (temp == tot && val[res] < val[MAX])) { tot = temp; MAX = res; } return MAX; } int main() { scanf("%d", &n); int id = 0; block = 30; num = n / block; if (n % block) { num++; } for (int i = 1; i <= n; i++) { scanf("%d", &a[i]); if (mp[a[i]] == 0) { mp[a[i]] = ++id; val[id] = a[i]; } belong[i] = (i - 1) / block + 1; a[i] = mp[a[i]]; v[a[i]].push_back(i); } for (int i = 1; i <= num; i++) { memset(cnt, 0, sizeof(cnt)); int MAX = 0, tot = 0; for (int j = (i - 1) * block + 1; j <= n; j++) { int temp = ++cnt[a[j]]; if (temp > tot || (temp == tot && val[a[j]] < val[MAX])) { tot = temp; MAX = a[j]; } mark[i][belong[j]] = MAX; } } for (int i = 1; i <= n; i++) { int l, r; scanf("%d%d", &l, &r); printf("%d\n", val[query(l, r)]); } return 0; }总结一下分块，那就是暴力哇，惹不起惹不起.jpg，溜了溜了。
转载于:https://www.cnblogs.com/Decray/p/10924593.html
相关资源：DirectX修复工具V4.0增强版