#分块
先上大佬博客
也不知道为什么我先学的莫队
生动形象的分块（三层的树）
假设我们总共的序列长度为n，然后我们把它切成n−−√n块，然后把每一块里的东西当成一个整体来看，
现在解释几个本文用到的术语：
完整块：被操作区间完全覆盖的块
不完整块：操作区间不完全覆盖的块
然后我们先看看怎么得出答案：
1.对于完整的块，我们希望有个东西能直接找出这整个块的和，于是每个块要维护这个块的所有元素的和。
.对于不完整块，因为元素比较少(最多有 总数n / 块数 = n−−√n 个) 这时候当n=1000000的时候最多有1000个，对比一下，我们可以直接暴力扫这个小块统计答案，
.小技巧：如果这个不完整块被覆盖的长度>块维护的长度的一半，何不用这个块的和-没有被覆盖的元素的值呢？
2.这里，我们换种思路，记录一个lazy 标记(为什么用lazy，因为我很懒),表示整个块被加上过多少了，
.对于完整块，我们直接lazy+=加上的数x,块内的和ans+=x*元素个数(因为每个元素都被加上了x)
.对于不完整块，直接暴力修改就好了，顺便可以把lazy标记清了。
题目列表
操作：区间加法，单点查值
#include <bits/stdc++.h> using namespace std; inline long long read() { //读入优化 long long x = 0; long long f = 1; char c = getchar(); while (c < ‘0‘ || c > ‘9‘) { if (c == ‘-‘) f = -f; c = getchar(); } while (c <= ‘9‘ && c >= ‘0‘) { x = x * 10 + c - ‘0‘; c = getchar(); } return x * f; } int n; int m; int opt, l, r, c; int z[500521]; //原数组 int pos[500521]; //存储每个点所在的块 int tag[500521]; //标记数组 void modify(int l, int r, int c) { if (pos[l] == pos[r]) //如果在同一个块内直接暴力修改 for (int i = l; i <= r; i++) z[i] += c; else { for (int i = l; i <= pos[l] * m; i++) //修改左边不在一整块中的部分 z[i] += c; for (int i = pos[l] + 1; i <= pos[r] - 1; i++) //标记每个块需要加上的值 tag[i] += c; for (int i = (pos[r] - 1) * m + 1; i <= r; i++) //修改右边不在一整块中的部分 z[i] += c; } } int main() { n = read(); m = sqrt(n); for (int i = 1; i <= n; i++) z[i] = read(); int bnum = ceil((double)n / m); //上取整函数 for (int i = 1; i <= bnum; i++) for (int j = (i - 1) * m + 1; j <= i * m; ++j) pos[j] = i; for (int i = 1; i <= n; i++) { opt = read(); if (opt == 0) { l = read(); r = read(); c = read(); modify(l, r, c); } if (opt == 1) { l = read(); r = read(); c = read(); printf("%d\n",z[r] + tag[pos[r]]); //最后输出的值就是该点的值加上该点所在块的标记值（即需要加上的值） } } return 0; }
操作：区间加法，询问区间内小于某个值 xxx 的元素个数
似乎并没有什么区别，主要就是多了一个reset函数，emm另外， lower_bound的特性利用也很重要
#include <bits/stdc++.h> using namespace std; inline long long read() { long long x = 0; long long f = 1; char c = getchar(); while (c < ‘0‘ || c > ‘9‘) { if (c == ‘-‘) f = -f; c = getchar(); } while (c <= ‘9‘ && c >= ‘0‘) { x = x * 10 + c - ‘0‘; c = getchar(); } return x * f; } long long n, m; long long opt, l, r, c; long long z[5211314]; long long pos[5211314]; long long tag[5211314]; vector<long long> v[1314]; void reset(long long x) { v[x].clear(); //清空该块内的元素 for (long long i = (x - 1) * m + 1; i <= x * m; i++) v[x].push_back(z[i]); sort(v[x].begin(), v[x].end()); } void modify(long long l, long long r, long long c) { //修改函数 if (pos[l] == pos[r]) { //在同一块内 for (long long i = l; i <= r; i++) z[i] += c; // 排序只是在vector中有序，因为是原数组修改，所以需要清空此块重新插入进行排序 reset(pos[l]); } else { for (long long i = l; i <= pos[l] * m; i++) z[i] += c; // 排序只是在vector中有序，因为是原数组修改，所以需要清空此块重新插入进行排序 reset(pos[l]); for (long long i = pos[l] + 1; i <= pos[r] - 1; i++) tag[i] += c; //对块进行标记时，区间加法并不会影响序列次序，所以只需要标记块 for (long long i = (pos[r] - 1) * m + 1; i <= r; i++) z[i] += c; // 排序只是在vector中有序，因为是原数组修改，所以需要清空此块重新插入进行排序 reset(pos[r]); } } long long query(long long l, long long r, long long f) { long long ans = 0; if (pos[l] == pos[r]) { for (long long i = l; i <= r; i++) if (z[i] + tag[pos[i]] < f) ans++; return ans; } else { for (long long i = l; i <= pos[l] * m; i++) if (z[i] + tag[pos[i]] < f) ans++; for (long long i = pos[l] + 1; i <= pos[r] - 1; i++) { long long t = f - tag[i]; // lowe_bound返回第一个大于或等于t的位置，减去begin得到区间内元素个数 ans += lower_bound(v[i].begin(), v[i].end(), t) - v[i].begin(); } for (long long i = (pos[r] - 1) * m + 1; i <= r; i++) if (z[i] + tag[pos[i]] < f) ans++; } return ans; } int main() { n = read(); m = sqrt(n); //预处理每个点所在的快 int bnum = ceil((double)n / m); //上取整函数 for (int i = 1; i <= bnum; i++) for (int j = (i - 1) * m + 1; j <= i * m; ++j) pos[j] = i; for (long long i = 1; i <= n; i++) { z[i] = read(); v[pos[i]].push_back(z[i]); } //利用sort把每个块内的数据排好序 begin和end 代表所要排序的范围即整个v[i][~]‘’ for (long long i = 1; i <= pos[n]; i++) sort(v[i].begin(), v[i].end()); for (long long i = 1; i <= n; i++) { opt = read(); if (opt == 0) { l = read(); r = read(); c = read(); modify(l, r, c); } if (opt == 1) { l = read(); r = read(); c = read(); printf("%lld\n", query(l, r, c * c)); } } return 0; }
毒瘤题玄学AC（我都不知道为什么要这么做改了一个晚上）
#include <bits/stdc++.h> using namespace std; inline long long read() { long long x = 0; long long f = 1; char c = getchar(); while (c < ‘0‘ || c > ‘9‘) { if (c == ‘-‘) f = -f; c = getchar(); } while (c <= ‘9‘ && c >= ‘0‘) { x = x * 10 + c - ‘0‘; c = getchar(); } return x * f; } long long n, m; long long opt, l, r, c; long long z[5211314]; long long pos[5211314]; long long tag[5211314]; vector<long long> v[1314]; void reset(long long x) { v[x].clear(); //清空该块内的元素 for (long long i = (x - 1) * m + 1; i <= x * m; i++) v[x].push_back(z[i]); sort(v[x].begin(), v[x].end()); } void modify(long long l, long long r, long long c) { //修改函数 if (pos[l] == pos[r]) { //在同一块内 for (long long i = l; i <= r; i++) z[i] += c; reset(pos[l]); } else { for (long long i = l; i <= pos[l] * m; i++) z[i] += c; // 排序只是在vector中有序，因为是原数组修改，所以需要清空此块重新插入进行排序 reset(pos[l]); for (long long i = pos[l] + 1; i <= pos[r] - 1; i++) tag[i] += c; //对块进行标记时，区间加法并不会影响序列次序，所以只需要标记块 for (long long i = (pos[r] - 1) * m + 1; i <= r; i++) z[i] += c; // 排序只是在vector中有序，因为是原数组修改，所以需要清空此块重新插入进行排序 reset(pos[r]); } } long long query(long long l, long long r, long long f) { long long ans = -1; if (pos[l] == pos[r]) { for (long long i = l; i <= r; i++) if (z[i] + tag[pos[i]] < c) ans = max(ans, z[i] + tag[pos[i]]); for (long long i = pos[l] + 1; i <= pos[r] - 1; i++) { long long t = c - tag[i]; long long size = lower_bound(v[i].begin(), v[i].end(), t) - v[i].begin(); if (size >= l && size <= r) ans = max(v[i][size - 1] + tag[i], ans); } return ans; } else { for (long long i = l; i <= pos[l] * m; i++) if (z[i] + tag[pos[i]] < c) ans = max(ans, z[i] + tag[pos[i]]); for (long long i = (pos[r] - 1) * m + 1; i <= r; i++) if (z[i] + tag[pos[i]] < c) ans = max(ans, z[i] + tag[pos[i]]); for (long long i = pos[l] + 1; i <= pos[r] - 1; i++) { long long t = c - tag[i]; long long size = lower_bound(v[i].begin(), v[i].end(), t) - v[i].begin(); if (size >= 1) ans = max(v[i][size - 1] + tag[i], ans); } } return ans; } int main() { n = read(); m = sqrt(n); int bnum = ceil((double)n / m); for (int i = 1; i <= bnum; i++) for (int j = (i - 1) * m + 1; j <= i * m; ++j) pos[j] = i; for (long long i = 1; i <= n; i++) { z[i] = read(); v[pos[i]].push_back(z[i]); } for (long long i = 1; i <= pos[n]; i++) sort(v[i].begin(), v[i].end()); for (long long i = 1; i <= n; i++) { opt = read(); if (opt == 0) { l = read(); r = read(); c = read(); modify(l, r, c); } if (opt == 1) { l = read(); r = read(); c = read(); printf("%lld\n", query(l, r, c)); } } return 0; }
原文：https://www.cnblogs.com/wilxx/p/11681351.html