3678 字
18 分钟
分块新刷
2026-06-12
学术
算法
NOTE

大概四年前给 loj 上的分块都板刷了一遍，但是上高中之后 AFO 后全忘了，最近重新复习一下发现洛谷出了分块板子题，就先写这个了。至于 loj 剩下的到时候再写吧。（我去 都四年了吗）

P13976 数列分块入门 1#

#define _CRT_SECURE_NO_WARNINGS

#include<iostream>
#include<math.h>
using namespace std;

#define int long long

const int maxn = 3e5 + 10;
int n;
int a[maxn];

int cnt, loc[maxn];
struct block {
	int add;
	int l, r;
} b[maxn];

void build() {
	cnt = sqrt(n);
	for (int i = 1; i < cnt; i++) {
		b[i].l = b[i - 1].r + 1;
		b[i].r = b[i].l + (int)sqrt(n) - 1;
		for (int j = b[i].l; j <= b[i].r; j++) {
			loc[j] = i;
		}
	}
	b[cnt].l = b[cnt - 1].r + 1;
	b[cnt].r = n;
	for (int i = b[cnt].l; i <= b[cnt].r; i++) {
		loc[i] = cnt;
	}
}

void add(int l, int r, int x) {
	if (loc[l] == loc[r]) {
		for (int i = l; i <= r; i++) a[i] += x;
		return;
	}
	for (int i = l; i <= b[loc[l]].r; i++) a[i] += x;
	for (int i = b[loc[r]].l; i <= r; i++) a[i] += x;
	for (int i = loc[l] + 1; i < loc[r]; i++) b[i].add += x;
}

int query(int x) {
	return a[x] + b[loc[x]].add;
}

signed main() {
	scanf("%lld", &n);
	for (int i = 1; i <= n; i++) {
		scanf("%lld", &a[i]);
	}
	build();
	//for (int i = 1; i <= cnt; i++) {
	//	printf("%d %d\n", b[i].l, b[i].r);
	//	printf("%d\n", b[i].add);
	//}
	//for (int i = 1; i <= n; i++) {
	//	printf("%lld ", a[i]);
	//}
	//printf("\n");
	for (int i = 1; i <= n; i++) {
		int opt, l, r, c;
		scanf("%lld%lld%lld%lld", &opt, &l, &r, &c);
		if (!opt) {
			add(l, r, c);
		}
		if (opt) {
			printf("%lld\n", query(r));
		}
		//for (int i = 1; i <= cnt; i++) {
		//	printf("%d %d\n", b[i].l, b[i].r);
		//	printf("%d\n", b[i].add);
		//}
		//for (int i = 1; i <= n; i++) {
		//	printf("%lld ", a[i]);
		//}
		//printf("\n");
	}
	return 0;
}

没看题解直接硬写，忘记了两个点：

  • 未标记 loc[] 导致不会做了
  • 标记 loc[] 的时候漏掉了 cnt

没别的问题了——2026.6.12

P13977 数列分块入门 2#

#define _CRT_SECURE_NO_WARNINGS

#include<iostream>
#include<set>
#include<cmath>
#include<algorithm>
using namespace std;

#define int long long

const int maxn = 2e5 + 10;

int n;
int a[maxn];
int sorted[maxn];

struct block {
	int l, r, add;
} b[maxn];
int cnt;
int loc[maxn];

void fix(int x) {
	for (int i = b[x].l; i <= b[x].r; i++) {
		sorted[i] = a[i];
	}
	sort(sorted + b[x].l, sorted + b[x].r + 1);
}

void build() {
	cnt = sqrt(n);
	for (int i = 1; i < cnt; i++) {
		b[i].l = b[i - 1].r + 1;
		b[i].r = b[i].l + cnt - 1;
		for (int j = b[i].l; j <= b[i].r; j++) {
			loc[j] = i;
		}
	}
	b[cnt].l = b[cnt - 1].r + 1;
	b[cnt].r = n;
	for (int i = b[cnt].l; i <= b[cnt].r; i++) {
		loc[i] = cnt;
	}
	for (int i = 1; i <= cnt; i++) fix(i);
}

void add(int l, int r, int x) {
	if (loc[l] == loc[r]) {
		for (int i = l; i <= r; i++) {
			a[i] += x;
		}
		fix(loc[l]);
		return;
	}

	for (int i = l; i <= b[loc[l]].r; i++) a[i] += x;
	fix(loc[l]);
	for (int i = b[loc[r]].l; i <= r; i++) a[i] += x;
	fix(loc[r]);
	for (int i = loc[l] + 1; i < loc[r]; i++) {
		b[i].add += x;
	}
}

int query(int l, int r, int c) {
	int ans = 0;
	if (loc[l] == loc[r]) {
		for (int i = l; i <= r; i++) {
			if (a[i] + b[loc[i]].add < c * c) {
				ans++;
			}
		}
		return ans;
	}

	for (int i = l; i <= b[loc[l]].r; i++) {
		if (a[i] + b[loc[i]].add < c * c) {
			ans++;
		}
	}
	for (int i = b[loc[r]].l; i <= r; i++) {
		if (a[i] + b[loc[i]].add < c * c) {
			ans++;
		}
	}
	for (int i = loc[l] + 1; i < loc[r]; i++) {
		int tmp = c * c - b[i].add;
		int t = lower_bound(sorted + b[i].l, sorted + b[i].r + 1, tmp) - sorted;
		ans += (t - b[i].l);
	}
	return ans;
}

signed main() {
	scanf("%lld", &n);
	for (int i = 1; i <= n; i++) {
		scanf("%lld", &a[i]);
	}
	build();
	for (int i = 1; i <= n; i++) {
		int opt, l, r, c;
		scanf("%lld%lld%lld%lld", &opt, &l, &r, &c);
		if (!opt) {
			add(l, r, c);
		}
		if (opt) {
			printf("%lld\n", query(l, r, c));
		}
	}
	return 0;
}

太抽象了这题，搞了我半个小时

一开始用 map，结果这玩意在这题二分不了。然后试了 multiset（AI 的推荐），结果发现还是有问题，multiset 我的 visual studio 始终无法接受两个迭代器相减这个能力。最后不得不尝试使用暴力排序原数组。本来以为会很慢，结果算了一下发现瓶颈才 O(nnlog⁡n)O(n\sqrt{n}\log n) ，没啥大问题。

但是犯了如下这些错误：

  • 不能直接排序 a[]，不然暴力弄散块的时候下标不对了，需要再定义一个数组 sorted[] 存排序后的 a[]
  • 整块不用重新排 sorted[]，只有散块需要。而且散块是整个块重排。

大概就这些，题不难，实现我整的有点费劲——2026.6.12

P13978 数列分块入门 3#

#define _CRT_SECURE_NO_WARNINGS

#include<iostream>
#include<set>
#include<cmath>
#include<algorithm>
#include<climits>
using namespace std;

#define int long long

const int maxn = 2e5 + 10;

int n;
int a[maxn];
int sorted[maxn];

struct block {
	int l, r, add;
} b[maxn];
int cnt;
int loc[maxn];

void fix(int x) {
	for (int i = b[x].l; i <= b[x].r; i++) {
		sorted[i] = a[i];
	}
	sort(sorted + b[x].l, sorted + b[x].r + 1);
}

void build() {
	cnt = sqrt(n);
	for (int i = 1; i < cnt; i++) {
		b[i].l = b[i - 1].r + 1;
		b[i].r = b[i].l + cnt - 1;
		for (int j = b[i].l; j <= b[i].r; j++) {
			loc[j] = i;
		}
	}
	b[cnt].l = b[cnt - 1].r + 1;
	b[cnt].r = n;
	for (int i = b[cnt].l; i <= b[cnt].r; i++) {
		loc[i] = cnt;
	}
	for (int i = 1; i <= cnt; i++) fix(i);
}

void add(int l, int r, int x) {
	if (loc[l] == loc[r]) {
		for (int i = l; i <= r; i++) {
			a[i] += x;
		}
		fix(loc[l]);
		return;
	}

	for (int i = l; i <= b[loc[l]].r; i++) a[i] += x;
	fix(loc[l]);
	for (int i = b[loc[r]].l; i <= r; i++) a[i] += x;
	fix(loc[r]);
	for (int i = loc[l] + 1; i < loc[r]; i++) {
		b[i].add += x;
	}
}

int query(int l, int r, int c) {
	int ans = LLONG_MIN + 10;
	//cout << ans << endl;
	if (loc[l] == loc[r]) {
		for (int i = l; i <= r; i++) {
			if (a[i] + b[loc[i]].add < c) {
				ans = max(ans, a[i] + b[loc[i]].add);
			}
		}
		if (ans == LLONG_MIN + 10) return -1;
		return ans;
	}

	for (int i = l; i <= b[loc[l]].r; i++) {
		if (a[i] + b[loc[i]].add < c) {
			ans = max(ans, a[i] + b[loc[i]].add);
		}
	}
	for (int i = b[loc[r]].l; i <= r; i++) {
		if (a[i] + b[loc[i]].add < c) {
			ans = max(ans, a[i] + b[loc[i]].add);
		}
	}
	for (int i = loc[l] + 1; i < loc[r]; i++) {
		int tmp = c - b[i].add;
		int t = lower_bound(sorted + b[i].l, sorted + b[i].r + 1, tmp) - sorted;
		if (t - 1 >= b[i].l) ans = max(ans, sorted[t - 1] + b[i].add);
	}
	if (ans == LLONG_MIN + 10) return -1;
	return ans;
}

signed main() {
	scanf("%lld", &n);
	for (int i = 1; i <= n; i++) {
		scanf("%lld", &a[i]);
	}
	build();
	for (int i = 1; i <= n; i++) {
		int opt, l, r, c;
		scanf("%lld%lld%lld%lld", &opt, &l, &r, &c);
		if (!opt) {
			add(l, r, c);
		}
		if (opt) {
			printf("%lld\n", query(l, r, c));
		}
	}
	return 0;
}

就是分块2的代码稍微改两下就行了，虽然我改了五次才过。。。——2026.6.12

P13979 数列分块入门 4#

#define _CRT_SECURE_NO_WARNINGS

#include<iostream>
#include<cmath>
using namespace std;
#define int long long

const int maxn = 3e5 + 10;

int n;
int a[maxn];

int cnt, f[maxn];
struct block {
	int l, r, sum, add;
} b[maxn];

void build() {
	cnt = sqrt(n);
	for (int i = 1; i < cnt; i++) {
		b[i].l = b[i - 1].r + 1;
		b[i].r = b[i].l + cnt - 1;
		b[i].add = 0;
		for (int j = b[i].l; j <= b[i].r; j++) {
			b[i].sum += a[j];
			f[j] = i;
		}
	}
	b[cnt].l = b[cnt - 1].r + 1;
	b[cnt].r = n;
	b[cnt].add = 0;
	for (int j = b[cnt].l; j <= b[cnt].r; j++) {
		b[cnt].sum += a[j];
		f[j] = cnt;
	}
}

void add(int l, int r, int c) {
	if (f[l] == f[r]) {
		for (int i = l; i <= r; i++) a[i] += c;
		b[f[l]].sum += c * (r - l + 1);
		return;
	}
	for (int i = l; i <= b[f[l]].r; i++) {
		a[i] += c;
	}
	b[f[l]].sum += c * (b[f[l]].r - l + 1);
	for (int i = b[f[r]].l; i <= r; i++) {
		a[i] += c;
	}
	b[f[r]].sum += c * (r - b[f[r]].l + 1);
	for (int i = f[l] + 1; i < f[r]; i++) {
		b[i].add += c;
	}
}

int query(int l, int r, int c) {
	int ans = 0;
	if (f[l] == f[r]) {
		for (int i = l; i <= r; i++) {
			ans += a[i] + b[f[i]].add;
		}
		ans = (ans % c + c) % c;
		return ans;
	}
	for (int i = l; i <= b[f[l]].r; i++) {
		ans += a[i] + b[f[i]].add;
	}
	for (int i = b[f[r]].l; i <= r; i++) {
		ans += a[i] + b[f[i]].add;
	}
	for (int i = f[l] + 1; i < f[r]; i++) {
		ans += b[i].sum + b[i].add * (b[i].r - b[i].l + 1);
	}
	ans = (ans % c + c) % c;
	return ans;
}

signed main() {
	scanf("%lld", &n);
	for (int i = 1; i <= n; i++) {
		scanf("%lld", &a[i]);
	}
	build();
	for (int i = 1; i <= n; i++) {
		int opt, l, r, c;
		scanf("%lld%lld%lld%lld", &opt, &l, &r, &c);
		if (!opt) {
			add(l, r, c);
		}
		if (opt) {
			c++;
			printf("%lld\n", query(l, r, c));
		}
	}
	return 0;
}

一遍就写对了，但是有几个点TLE。后来发现是因为我 ans = (ans % c + c) % c; 太多次了导致常数太大。。。（看题解才知道的）

不知道这种情况以后会不会阴我一手。。。——2026.6.12

P13980 数列分块入门 5#

#define _CRT_SECURE_NO_WARNINGS

#include<iostream>
#include<cmath>
using namespace std;
#define int long long

const int maxn = 3e5 + 10;
int n;
int a[maxn];

int cnt, f[maxn];
struct block {
	bool noupdate = true;
	int l, r;
	int sum;
} b[maxn];

void refresh(int id) {
	b[id].noupdate = 1;
	b[id].sum = 0;
	for (int i = b[id].l; i <= b[id].r; i++) {
		if (a[i] != 1 && a[i] != 0) {
			b[id].noupdate = 0;
		}
		b[id].sum += a[i];
	}
}

void build() {
	cnt = (int)sqrt(n);
	for (int i = 1; i < cnt; i++) {
		b[i].l = b[i - 1].r + 1;
		b[i].r = b[i].l + cnt - 1;
		for (int j = b[i].l; j <= b[i].r; j++) {
			b[i].sum += a[j];
			f[j] = i;
			if (a[j] != 1 && a[j] != 0) b[i].noupdate = false;
		}
	}

	b[cnt].l = b[cnt - 1].r + 1;
	b[cnt].r = n;
	for (int j = b[cnt].l; j <= b[cnt].r; j++) {
		b[cnt].sum += a[j];
		f[j] = cnt;
		if (a[j] != 1 && a[j] != 0) b[cnt].noupdate = false;
	}
}

void update(int l, int r) {
	if (f[l] == f[r]) {
		if (b[f[l]].noupdate) return;
		for (int i = l; i <= r; i++) {
			a[i] = (int)sqrt(a[i]);
		}
		refresh(f[l]);
		return;
	}

	if (!b[f[l]].noupdate) {
		for (int i = l; i <= b[f[l]].r; i++) {
			a[i] = (int)sqrt(a[i]);
		}
		refresh(f[l]);
	}
	if (!b[f[r]].noupdate) {
		for (int i = b[f[r]].l; i <= r; i++) {
			a[i] = (int)sqrt(a[i]);
		}
		refresh(f[r]);
	}
	for (int i = f[l] + 1; i < f[r]; i++) {
		if (!b[i].noupdate) {
			for (int j = b[i].l; j <= b[i].r; j++) {
				a[j] = (int)sqrt(a[j]);
			}
			refresh(i);
		}
	}
}

int query(int l, int r) {
	int ans = 0;
	if (f[l] == f[r]) {
		for (int i = l; i <= r; i++) {
			ans += a[i];
		}
		return ans;
	}

	for (int i = l; i <= b[f[l]].r; i++) {
		ans += a[i];
	}
	for (int i = b[f[r]].l; i <= r; i++) {
		ans += a[i];
	}
	for (int i = f[l] + 1; i < f[r]; i++) {
		ans += b[i].sum;
	}
	return ans;
}

signed main() {
	scanf("%lld", &n);
	for (int i = 1; i <= n; i++) {
		scanf("%lld", &a[i]);
	}
	build();

	for (int i = 1; i <= n; i++) {
		int opt, l, r;
		scanf("%lld%lld%lld", &opt, &l, &r);
		if (!opt) update(l, r);
		if (opt) printf("%lld\n", query(l, r));
	}
	return 0;
}

这题我熟啊，应该是两年前打过一个计蒜客的比赛，那个是开立方根，然后洛谷好像还有一道也是开平方根，但是我当时用的是线段树。

犯的错：没考虑 0 开根号也是 0，不用 update 了。没考虑最后一个点会被卡 TLE。——2026.6.12

P13981 数列分块入门 6#

#define _CRT_SECURE_NO_WARNINGS

#include<iostream>
#include<cmath>
#include<vector>
using namespace std;

#define int long long

const int maxn = 3e5 + 10;
int n;
int a[maxn];

int cnt, f[maxn];
struct block {
	vector<int> v;
	int l, r;
} b[600];

void build() {
	cnt = sqrt(n);
	for (int i = 1; i < cnt; i++) {
		b[i].l = b[i - 1].r + 1;
		b[i].r = b[i].l + cnt - 1;
		for (int j = b[i].l; j <= b[i].r; j++) {
			b[i].v.push_back(a[j]);
			f[j] = i;
		}
	}
	b[cnt].l = b[cnt - 1].r + 1;
	b[cnt].r = n;
	for (int j = b[cnt].l; j <= b[cnt].r; j++) {
		b[cnt].v.push_back(a[j]);
		f[j] = cnt;
	}
}

void update(int x, int v) {
	for (int i = 1; i <= cnt; i++) {
		if (x > b[i].v.size()) {
			x -= b[i].v.size();
		}
		else {
			b[i].v.insert(b[i].v.begin() + x - 1, v);
			break;
		}
	}
}

int query(int x) {
	for (int i = 1; i <= cnt; i++) {
		if (x > b[i].v.size()) {
			x -= b[i].v.size();
		}
		else {
			return b[i].v[x - 1];
		}
	}
}

void prv() {
	return;
	cout << "PRV(): ";
	for (int i = 1; i <= cnt; i++) {
		for (auto k : b[i].v) {
			cout << k << ' ';
		}
	}
	cout << endl;
}

signed main() {
	scanf("%lld", &n);
	for (int i = 1; i <= n; i++) {
		scanf("%lld", &a[i]);
	}
	build();
	for (int i = 1; i <= n; i++) {
		int opt, l, r, c;
		scanf("%lld", &opt);

		if (!opt) {
			scanf("%lld%lld", &l, &r);
			update(l, r);
			prv();
		}
		if (opt) {
			scanf("%lld", &c);
			printf("%lld\n", query(c));
		}
	}
	return 0;
}

没想到这么朴素的做法都直接过了。。。我看题解说还要重构。。。数据太弱了吧，虽然当初我在 loj 用 vector 都直接过了。。。

我再试试要重构的。

好了，写出来了：

#define _CRT_SECURE_NO_WARNINGS

#include<iostream>
#include<cmath>
#include<vector>
#include<cstring>
#include<string>
using namespace std;

#define int long long

const int maxn = 3e5 + 10;
int n, nn;
int a[maxn * 3];

int rebuild;

int cnt;
struct block {
	vector<int> v;
	int l, r;
} b[maxn * 3];

void build() {
	int tmp = 0;
	for (int i = 1; i <= cnt; i++) {
		for (auto k : b[i].v) {
			a[++tmp] = k;
		}
	}
	cnt = sqrt(nn);
	for (int i = 1; i < cnt; i++) {
		b[i].l = b[i - 1].r + 1;
		b[i].r = b[i].l + cnt - 1;
		b[i].v.clear();
		for (int j = b[i].l; j <= b[i].r; j++) {
			b[i].v.push_back(a[j]);
		}
	}
	b[cnt].l = b[cnt - 1].r + 1;
	b[cnt].r = nn;
	b[cnt].v.clear();
	for (int j = b[cnt].l; j <= b[cnt].r; j++) {
		b[cnt].v.push_back(a[j]);
	}
}

void update(int x, int v) {
	for (int i = 1; i <= cnt; i++) {
		if (x > b[i].v.size()) {
			x -= b[i].v.size();
		}
		else {
			b[i].v.insert(b[i].v.begin() + x - 1, v);
			break;
		}
	}
}

int query(int x) {
	for (int i = 1; i <= cnt; i++) {
		if (x > b[i].v.size()) {
			x -= b[i].v.size();
		}
		else {
			return b[i].v[x - 1];
		}
	}
}

void prv() {
	return;
	cout << "PRV(): ";
	for (int i = 1; i <= cnt; i++) {
		for (auto k : b[i].v) {
			cout << k << ' ';
		}
	}
	cout << endl;
}

signed main() {
	scanf("%lld", &n);
	nn = n;
	for (int i = 1; i <= n; i++) {
		scanf("%lld", &a[i]);
	}
	build();
	rebuild = sqrt(n);
	for (int i = 1; i <= n; i++) {
		if (rebuild == 0) {
			build();
			rebuild = sqrt(n);
		}
		rebuild--;
		int opt, l, r, c;
		scanf("%lld", &opt);

		if (!opt) {
			scanf("%lld%lld", &l, &r);
			update(l, r);
			nn++;
			prv();
		}
		if (opt) {
			scanf("%lld", &c);
			printf("%lld\n", query(c));
		}
	}
	return 0;
}

但是貌似反而跑的更慢了？？？

无所谓了，就当学个思想。

犯了好几次重构忘记清空的问题了，太蠢了。——2026.6.12

P13982 数列分块入门 7#

#define _CRT_SECURE_NO_WARNINGS

#include<iostream>
#include<cmath>
using namespace std;

#define int long long

const int maxn = 3e5 + 10;
const int m = 10007;

int n;
int a[maxn];

int cnt, f[maxn];
struct block {
	int l = 0, r = 0, add = 0, times = 1;
} b[maxn];

void build() {
	cnt = sqrt(n);
	for (int i = 1; i < cnt; i++) {
		b[i].l = b[i - 1].r + 1;
		b[i].r = b[i].l + cnt - 1;
		for (int j = b[i].l; j <= b[i].r; j++) {
			f[j] = i;
		}
	}

	b[cnt].l = b[cnt - 1].r + 1;
	b[cnt].r = n;
	for (int j = b[cnt].l; j <= b[cnt].r; j++) {
		f[j] = cnt;
	}
}

void update(int x) {
	for (int i = b[x].l; i <= b[x].r; i++) {
		a[i] *= b[x].times;
		a[i] %= m;
		a[i] += b[x].add;
		a[i] %= m;
	}
	b[x].times = 1, b[x].add = 0;
}

void add(int l, int r, int c) {
	if (f[l] == f[r]) {
		update(f[l]);
		for (int i = l; i <= r; i++) {
			a[i] += c;
			a[i] %= m;
		}
		return;
	}
	update(f[l]);
	update(f[r]);
	for (int i = l; i <= b[f[l]].r; i++) {
		a[i] += c;
		a[i] %= m;
	}
	for (int i = b[f[r]].l; i <= r; i++) {
		a[i] += c;
		a[i] %= m;
	}
	for (int i = f[l] + 1; i < f[r]; i++) {
		b[i].add += c;
		b[i].add %= m;
	}
}

void times(int l, int r, int c) {
	if (f[l] == f[r]) {
		update(f[l]);
		for (int i = l; i <= r; i++) {
			a[i] *= c;
			a[i] %= m;
		}
		return;
	}
	update(f[l]);
	update(f[r]);
	for (int i = l; i <= b[f[l]].r; i++) {
		a[i] *= c;
		a[i] %= m;
	}
	for (int i = b[f[r]].l; i <= r; i++) {
		a[i] *= c;
		a[i] %= m;
	}
	for (int i = f[l] + 1; i < f[r]; i++) {
		b[i].add *= c;
		b[i].add %= m;
		b[i].times *= c;
		b[i].times %= m;
	}
}

int query(int x) {
	int tmp = a[x] * b[f[x]].times + b[f[x]].add;
	return (tmp % m + m) % m;
}

signed main() {
	scanf("%lld", &n);
	for (int i = 1; i <= n; i++) {
		scanf("%lld", &a[i]);
	}
	build(); 

	for (int i = 1; i <= n; i++) {
		int opt, l, r, c;
		scanf("%lld%lld%lld%lld", &opt, &l, &r, &c);
		if (opt == 0) {
			add(l, r, c);
		}
		if (opt == 1) {
			times(l, r, c);
		}
		if (opt == 2) {
			printf("%lld\n", query(r));
		}
	}
	return 0;
}

压力，除了编译错误和忘了取余直接过了 XD

没啥难度，跟线段树模板一样，还没那个难，哪来的绿题。。。考虑一下懒惰标记的更新顺序就行。然后这里头 update 其实就是线段树里的 pushdown，下方懒惰标记来暴力。——2026.6.12

分块新刷
https://blog.mitufun.top/posts/分块新刷/
作者
MituFun
发布于
2026-06-12
许可协议
CC BY-NC-SA 4.0
PIP 问题
© 2026 MituFun. All Rights Reserved. / RSS / Sitemap
Powered by Astro & Fuwari