分块入门
1. 数列分块入门 1
题目：给定一个长度为 \(n\) 的数组 \(a\) 和 \(m\) 次操作，要求支持区间加法和单点查询。\(1\le n,m\le 5\times 10^4\)，答案及其他变量都在 int 范围内。
思路：
我们定义，\(p\) 表示块的长度，通常取 \(p=\sqrt{n}\)；\(block_i\) 表示第 \(i\) 个元素的块号，\(L_i\) 表示第 \(i\) 个元素所在的块的左端点，\(R_i\) 表示第 \(i\) 个元素所在的块的右端点，显然有 \(block_i=\left\lfloor\dfrac{i+p-1}{p}\right\rfloor,L_i=(block_i-1)\times p+1,R_i=\min(block_i\times p,n)\)；\(addtag_{i}\) 表示第 \(i\) 个块被增加的值。
对于区间加法，若 \(l,r\) 在同一块内则暴力处理；否则将左右两端的零散块暴力处理，中间的整块的 \(addtag\) 加上 \(c\) 即可。单点查询很简单，就是 \(a_r+addtag_{block_r}\)（暴力修改后的值加上所在块整体加的值）。
代码：
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
const int N = 5e4+10;
int n, p;
int a[N], block[N], L[N], R[N], addtag[N];
void add(int l, int r, int c) {
if (block[r] - block[l] < 1) {
for (int j = l; j <= r; ++j) a[j] += c;
} else {
for (int j = l; j <= R[l]; ++j) a[j] += c;
for (int j = L[r]; j <= r; ++j) a[j] += c;
for (int j = block[l]+1; j < block[r]; ++j) addtag[j] += c;
}
}
int query(int r) {
return a[r]+addtag[block[r]];
}
int main() {
scanf("%d", &n);
p = sqrt(n);
for (int i = 1; i <= n; ++i) {
scanf("%d", &a[i]);
block[i] = (i+p-1) / p, L[i] = p * (block[i]-1) + 1, R[i] = min(p*block[i], n);
}
for (int i = 1; i <= n; ++i) {
int opt, l, r, c;
scanf("%d%d%d%d", &opt, &l, &r, &c);
if (!opt) add(l, r, c);
else printf("%d\n", query(r));
}
return 0;
}
题目：给定一个长度为 \(n\) 的数组 \(a\) 和 \(m\) 次操作，要求支持区间加法和区间查询。\(1\le n,m\le 10^5\)，任何时刻数列中所有元素的绝对值之和不超过 \(10^{18}\)。
思路：
定义 \(s_i\) 表示第 \(i\) 个块内所有元素的和。考虑如何维护：
- \(l,r\) 在同一块内：暴力修改，注意同时更新 \(s_{block_i}\)；
- 否则将两边的散块暴力修改，中间的整块的 \(addtag\) 加上 \(c\)。
接着考虑如何回答询问：
- \(l,r\) 在同一块内：暴力计算。
- 否则暴力计算两边的散块，中间每一个整块的贡献为 \(s_i+addtag_{i}\times p\)。
代码和上面的很像，就不贴了。
练习：P3870, P1471（你可能需要推一下式子然后维护一些奇怪的东西）。
2. 数列分块入门 2
题目：给定一个长度为 \(n\) 的数组 \(a\) 和 \(m\) 次操作，要求支持区间加法和查询区间内小于 \(c^2\) 的元素个数。\(1\le n,m\le 5\times 10^4\)，答案及其他变量都在 int 范围内。
思路：
我们用块的个数个 vector 来存储每一个整块内所有元素从小到大排好序的值。
如何维护：
- \(l,r\) 在同一块内：暴力修改，同时将 \(l,r\) 所在的块先清空，重新插入后再排序。
- 否则将两边的散块暴力修改，中间的整块的 \(addtag\) 加上 \(c\)。
回答询问：
- \(l,r\) 在同一块内：暴力统计。
- 否则两边的散块暴力统计，中间的整块利用
lower_bound函数找到第一个大于等于 \(c^2-addtag_i\) 的位置 \(pos\)，其对答案的贡献即为 \(pos\)。
代码：
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;
typedef long long ll;
const int N = 5e4+10;
int n, p;
int a[N], block[N], L[N], R[N], addtag[N];
vector<int> v[N];
void reset(int num) {
v[num].clear();
for (int i = (num-1)*p+1; i <= min(num*p, n); ++i)
v[num].push_back(a[i]);
sort(v[num].begin(), v[num].end());
}
void add(int l, int r, int c) {
if (block[r] == block[l]) {
for (int i = l; i <= r; ++i) a[i] += c;
reset(block[l]);
} else {
for (int i = l; i <= R[l]; ++i) a[i] += c;
reset(block[l]);
for (int i = L[r]; i <= r; ++i) a[i] += c;
reset(block[r]);
for (int i = block[l]+1; i < block[r]; ++i) addtag[i] += c;
}
}
int query(int l, int r, ll c) {
if (block[r] == block[l]) {
int cnt = 0;
for (int i = l; i <= r; ++i) if ((ll)a[i]+addtag[block[i]] < c) cnt ++;
return cnt;
} else {
int cnt = 0;
for (int i = l; i <= R[l]; ++i) if ((ll)a[i]+addtag[block[i]] < c) cnt ++;
for (int i = L[r]; i <= r; ++i) if ((ll)a[i]+addtag[block[i]] < c) cnt ++;
for (int i = block[l]+1; i < block[r]; ++i) cnt += lower_bound(v[i].begin(), v[i].end(), c-addtag[i]) - v[i].begin();
return cnt;
}
}
int main() {
scanf("%d", &n); p =sqrt(n);
for (int i = 1; i <= n; ++i) {
scanf("%d", &a[i]);
block[i] = (i+p-1) / p, L[i] = (block[i]-1)*p + 1, R[i] = min(block[i]*p, n);
v[block[i]].push_back(a[i]);
}
for (int i = 1; i <= block[n]; ++i) sort(v[i].begin(), v[i].end());
int op, l, r, c;
for (int i = 1; i <= n; ++i) {
scanf("%d%d%d%d", &op, &l, &r, &c);
if (!op) add(l, r, c);
else printf("%d\n", query(l, r, (ll)c*c));
}
return 0;
}
练习题：P2801（其实和上面那个几乎一模一样
未完待续 qwq
标签：入门,分块,int,include,addtag,block,暴力 From： https://www.cnblogs.com/Jasper08/p/16960680.html