分块

分块

分块是一种思想，名为分块思想。

顾名思义，把一个东西分成一些块来解决问题。通常为预处理每个块再修改或查询。

通常，我们把它长度定为 $len = \sqrt{n}$，一共有 $num = n \div len$ 段。

预处理

定义 $L_i$ 为第 $i$ 段的左端点，$R_i$ 为第 $i$ 段的右端点。则第 $i$ 段的左端点为 $(i - 1) \times len + 1$，右端点为 $i \times len$。$pos_i$ 为第 $i$ 个数属于第 $pos_i$ 个块。

注意：在最后一段长度不足 $len$，即多为最后几个剩余的元素多开了一个块时，$R_{num} > n$，需要特殊判断。

修改

对于一段区间 $[l,r]$，会有一些完整的块（可能没有）与两段散块分别分布在 $[l,R_{pos_l}]$ 与 $[L_{pos_r},r]$（可能没有）。

对于散块，我们直接暴力处理。

其余的完整的块，我们对他进行懒标记，等查询时再对其进行操作。

注意：当 $pos_l = pos_r$ 时，证明两端在一个段中，只需要暴力处理就行。

查询

依然按照上面的原理，找出散块和完整的块。

对于散块，依然暴力，还要加上懒标记乘上散块的长度。

其余的完整的块，直接获取块的值再加上懒标记乘上完整块的长度即可。

注意：当 $pos_l = pos_r$ 时，证明两端在一个段中，只需要暴力处理就行。

U522567 ١١(❛ᴗ❛)【分块】-区间修改，单点查询（数据需要加强）

单点查询就更简单了，答案就是数组当前点的值加上当前点所在块的懒标记。

#include <bits/stdc++.h>
#define int long long

using namespace std;

const int N = 5e4 + 10;

int n, m, L[N], R[N], pos[N], lazy[N], sum[N], a[N];

void init() {
	int len = sqrt(n);
	int num = n / len;
	if (n % len != 0) {
		num++;
	}
	for (int i = 1; i <= num; i++) {
		L[i] = (i - 1) * len + 1;
		R[i] = i * len;
	}
	if (R[num] > n) {
		R[num] = n;
	}
	for (int i = 1; i <= num; i++) {
		for (int j = L[i]; j <= R[i]; j++) {
			pos[j] = i;
			sum[i] += a[j];
		}
	}
}

void change(int l, int r, int val) {
	int p = pos[l], q = pos[r];
	if (p == q) {
		for (int i = l; i <= r; i++) {
			a[i] += val;
		}
		sum[p] += (r - l + 1) * val;
	} else {
		for (int i = l; i <= R[p]; i++) {
			a[i] += val;
		}
		sum[p] += (R[p] - l + 1) * val;
		for (int i = L[q]; i <= r; i++) {
			a[i] += val;
		}
		sum[q] += (r - L[q] + 1) * val;
		for (int i = p + 1; i <= q - 1; i++) {
			lazy[i] += val;
		}
	}
}

int query(int x) {
	int p = pos[x], q = pos[x], ans = 0;
//	if (p == q) {
		ans += a[x];
		ans += lazy[p] * 1;
//	} else {
//		for (int i = l; i <= R[p]; i++) {
//			ans += a[i];
//		}
//		ans += (R[p] - l + 1) * lazy[p];
//		for (int i = L[q]; i <= r; i++) {
//			ans += a[i];
//		}
//		ans += (r - L[q] + 1) * lazy[q];
//		for (int i = p + 1; i <= q - 1; i++) {
//			ans += sum[i] * lazy[i] * (R[i] - L[i] + 1);
//		}
//	}
	return ans;
}

signed main() {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	init();
	while (n--) {
		int op, l, r, c;
		cin >> op >> l >> r >> c;
		if (!op) {
			change(l, r, c);
		} else {
			cout << query(r) << '\n';
		}
	}
	return 0;
} 

U522568 ١١(❛ᴗ❛)【分块】-区间修改，区间查询

只需要最后模 $c + 1$ 即可。

#include <bits/stdc++.h>
#define int long long

using namespace std;

const int N = 5e4 + 10;

int n, m, L[N], R[N], pos[N], lazy[N], sum[N], a[N];

void init() {
	int len = sqrt(n);
	int num = n / len;
	if (n % len != 0) {
		num++;
	}
	for (int i = 1; i <= num; i++) {
		L[i] = (i - 1) * len + 1;
		R[i] = i * len;
	}
	if (R[num] > n) {
		R[num] = n;
	}
	for (int i = 1; i <= num; i++) {
		for (int j = L[i]; j <= R[i]; j++) {
			pos[j] = i;
			sum[i] += a[j];
		}
	}
}

void change(int l, int r, int val) {
	int p = pos[l], q = pos[r];
	if (p == q) {
		for (int i = l; i <= r; i++) {
			a[i] += val;
		}
		sum[p] += (r - l + 1) * val;
	} else {
		for (int i = l; i <= R[p]; i++) {
			a[i] += val;
		}
		sum[p] += (R[p] - l + 1) * val;
		for (int i = L[q]; i <= r; i++) {
			a[i] += val;
		}
		sum[q] += (r - L[q] + 1) * val;
		for (int i = p + 1; i <= q - 1; i++) {
			lazy[i] += val;
		}
	}
}

int query(int l, int r) {
	int p = pos[l], q = pos[r], ans = 0;
	if (p == q) {
		for (int i = l; i <= r; i++) {
			ans += a[i];
		}
		ans += lazy[p] * (r - l + 1);
	} else {
		for (int i = l; i <= R[p]; i++) {
			ans += a[i];
		}
		ans += (R[p] - l + 1) * lazy[p];
		for (int i = L[q]; i <= r; i++) {
			ans += a[i];
		}
		ans += (r - L[q] + 1) * lazy[q];
		for (int i = p + 1; i <= q - 1; i++) {
			ans += sum[i] + lazy[i] * (R[i] - L[i] + 1);
		}
	}
	return ans;
}

signed main() {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	init();
	while (n--) {
		int op, l, r, c;
		cin >> op >> l >> r >> c;
		if (!op) {
			change(l, r, c);
		} else {
			cout << query(l, r) % (c + 1) << '\n';
		}
	}
	return 0;
} 

P2357 守墓人

建议降黄。

相当于单点修改，单点查询，区间查询，区间修改。

#include <bits/stdc++.h>
#define int long long

using namespace std;

const int N = 2e5 + 10;

int n, m, L[N], R[N], pos[N], lazy[N], sum[N], a[N];

void init() {
	int len = sqrt(n);
	int num = n / len;
	if (n % len != 0) {
		num++;
	}
	for (int i = 1; i <= num; i++) {
		L[i] = (i - 1) * len + 1;
		R[i] = i * len;
	}
	if (R[num] > n) {
		R[num] = n;
	}
	for (int i = 1; i <= num; i++) {
		for (int j = L[i]; j <= R[i]; j++) {
			pos[j] = i;
			sum[i] += a[j];
		}
	}
}

void change(int l, int r, int val) {
	int p = pos[l], q = pos[r];
	if (p == q) {
		for (int i = l; i <= r; i++) {
			a[i] += val;
		}
		sum[p] += (r - l + 1) * val;
	} else {
		for (int i = l; i <= R[p]; i++) {
			a[i] += val;
		}
		sum[p] += (R[p] - l + 1) * val;
		for (int i = L[q]; i <= r; i++) {
			a[i] += val;
		}
		sum[q] += (r - L[q] + 1) * val;
		for (int i = p + 1; i <= q - 1; i++) {
			lazy[i] += val;
		}
	}
}

int query(int l, int r) {
	int p = pos[l], q = pos[r], ans = 0;
	if (p == q) {
		for (int i = l; i <= r; i++) {
			ans += a[i];
		}
		ans += lazy[p] * (r - l + 1);
	} else {
		for (int i = l; i <= R[p]; i++) {
			ans += a[i];
		}
		ans += (R[p] - l + 1) * lazy[p];
		for (int i = L[q]; i <= r; i++) {
			ans += a[i];
		}
		ans += (r - L[q] + 1) * lazy[q];
		for (int i = p + 1; i <= q - 1; i++) {
			ans += sum[i] + lazy[i] * (R[i] - L[i] + 1);
		}
	}
	return ans;
}

signed main() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	init();
	while (m--) {
		int op;
		cin >> op;
		if (op == 1) {
			int l, r, k;
			cin >> l >> r >> k;
			change(l, r, k);
		} else if (op == 2) {
			int k;
			cin >> k;
			a[1] += k;
		} else if (op == 3) {
			int k;
			cin >> k;
			a[1] -= k;
		} else if (op == 4) {
			int l, r;
			cin >> l >> r;
			cout << query(l, r) << '\n';
		} else {
			cout << a[1] << '\n';
		}
	}
	return 0;
} 

U522569 ١١(❛ᴗ❛)【分块】-区间修改，区间小值查询

对块里的数进行排序。修改时，散块暴力，其余的懒标记，且对其重新排序。查询时，散块暴力，其余的，因为有懒标记，所以实际要找的数是 $k - lazy_i$，再 lower_bound 即可。

#include <bits/stdc++.h>

using namespace std;

const int N = 2e5 + 10;

int n, m, L[N], R[N], pos[N], lazy[N], sum[N], a[N];
vector<int> G[N];

void init() {
	int len = sqrt(n);
	int num = n / len;
	if (n % len != 0) {
		num++;
	}
	for (int i = 1; i <= num; i++) {
		L[i] = (i - 1) * len + 1;
		R[i] = i * len;
	}
	R[num] = n;
	for (int i = 1; i <= num; i++) {
		for (int j = L[i]; j <= R[i]; j++) {
			pos[j] = i;
			G[i].push_back(a[j]);
		}
		sort(G[i].begin(), G[i].end());
	}
}

void EA(int l, int r, int k) {
	int p = pos[l];
	for (int i = l; i <= r; i++) {
		a[i] += k;
	}
	G[p].clear();
	for (int i = L[p]; i <= R[p]; i++) {
		G[p].push_back(a[i]);
	}
	sort (G[p].begin(), G[p].end());
}

void change(int l, int r, int val) {
	int p = pos[l], q = pos[r];
	if (p == q) {
		EA(l, r, val);
		return;
	}
	EA(l, R[p], val);
	EA(L[q], r, val);
	for (int i = p + 1; i <= q - 1; i++) {
		lazy[i] += val;
	}
}

int query(int l, int r, int k) {
	vector<int> v;
	for (int i = l; i <= r; i++) {
		v.push_back(a[i] + lazy[pos[l]]);
	}
	sort(v.begin(), v.end());
	return lower_bound(v.begin(), v.end(), k) - v.begin();
}

int ask(int l, int r, int k) {
	int p = pos[l], q = pos[r];
	if (p == q) {
		return query(l, r, k);
	}
	int ans = 0;
	ans += query(l, R[p], k) + query(L[q], r, k);
	for (int i = p + 1; i <= q - 1; i++) {
		ans += lower_bound(G[i].begin(), G[i].end(), k - lazy[i]) - G[i].begin();
	} 
	return ans;
}

signed main() {
    cin.tie(0), cout.tie(0)->sync_with_stdio(false);
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	init();
	while (n--) {
		int op, l, r, k;
		cin >> op >> l >> r >> k;
		if (op == 0) {
			change(l, r, k);
		} else {
			cout << ask(l, r, k * k) << '\n';
		}
	}
	return 0;
}