分块入门
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