块状数组&莫队学习笔记

本博客从入门级到 Ynoi 全覆盖 (确信),欢迎评论、点赞、转发!(日常营销号)

如果以下内容有错误,欢迎指出!转载全文或部分前请先联系作者。

同步发布于洛谷博客


0x1 分块&块状数组

分块,顾名思义,就是将原数列分成若干块(一般取 n\sqrt{n} 左右,可以动态也可以取常数),进行的快速统计的方法。块状数组类似于线段树,维护区间的信息。

例题 1:P3372 【模板】线段树 1

(好好写线段树它不香吗)

由于块状数组的复杂度不正确,不保证此做法能在任意时刻通过此题,仅以此题为例讲解思路。

AC 记录:线段树 | 分块

我们将原数列分成块长为 320320 的若干个块,对于每一块,我们记录一个块内的和和一个懒标记。修改时,若左右端点在同一块,直接暴力修改原数组和分块;若不在同一块,暴力修改左右零散块,中间整块修改块内的和以及懒标记。查询时类似,记得懒标记下放。

时间复杂度为 O(nn)O(n\sqrt{n})

容易写出代码:

//By: [email protected]_er(122461)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N = 1e5+5, SIZE = 320, K = 320;

ll n, m, a[N], s[K], tag[K], L[K], R[K], tot;
#define whichBlock(x) (\
	(x-1)/SIZE+1\
)
void initBlock() {
	tot = whichBlock(n);
	for(ll i=1;i<=tot;i++) {
		L[i] = R[i-1] + 1;
		R[i] = i * SIZE;
		for(ll j=L[i];j<=min(R[i],n);j++) s[i] += a[j];
	}
	R[tot] = n;
}
void pushdown(ll u) {
	ll X = whichBlock(u);
	if(!tag[X]) return;
	for(ll i=L[X];i<=R[X];i++) a[i] += tag[X];
	tag[X] = 0;
}
void modify(ll l, ll r, ll k) {
	ll X = whichBlock(l), Y = whichBlock(r);
	if(X == Y) for(ll i=l;i<=r;i++) a[i] += k, s[X] += k;
	else {
		for(ll i=l;i<=R[X];i++) a[i] += k, s[X] += k;
		for(ll i=X+1;i<Y;i++) tag[i] += k, s[i] += (R[i] - L[i] + 1) * k;
		for(ll i=L[Y];i<=r;i++) a[i] += k, s[Y] += k;
	}
}
ll query(ll l, ll r) {
	ll X = whichBlock(l), Y = whichBlock(r), ans = 0;
	if(X == Y) {
		pushdown(l);
		for(ll i=l;i<=r;i++) ans += a[i];
	}
	else {
		pushdown(l);
		for(ll i=l;i<=R[X];i++) ans += a[i];
		for(ll i=X+1;i<Y;i++) ans += s[i];
		pushdown(r);
		for(ll i=L[Y];i<=r;i++) ans += a[i];
	}
	return ans;
}

int main() {
	scanf("%lld%lld", &n, &m);
	for(ll i=1;i<=n;i++) scanf("%lld", &a[i]);
	initBlock();
	while(m--) {
		ll op, l, r, x;
		scanf("%lld%lld%lld", &op, &l, &r);
		if(op == 1) {
			scanf("%lld", &x);
			modify(l, r, x);
		}
		else printf("%lld\n", query(l, r));
	}
	return 0;
}

【完结撒花!】

其实分块大概就是这样,基础部分练习完了,我们来看几道习题。

部分习题有题解,不做额外讲解;其他的大概提思路。

习题 1:P5309 [Ynoi2011]初始化 | 题解

习题 2:P5356 [Ynoi2017]由乃打扑克 | 题解

0x2 莫队

例题 1:P1972 [SDOI2009]HH的项链

不过这题好像把莫队卡了,那就好好用树状数组吧。

没关系,我们有双倍经验。

例题 1.5:SP3267 DQUERY - D-query

统计区间内颜色个数,怎么办呢?

我们考虑暴力。每次暴力统计一遍太费时间了,我们搞两个指针,表示当前统计到的区间,然后在用一个数组存每个颜色在区间内有多少个,一个变量存区间内有多少颜色即可。统计到下一个区间,我们移动这两个指针(实时更新数组内的值),通过上面提到的数组来更新变量(颜色)的值。

但是这样很容易被卡:询问 [1,1],[n,n],[2,2],[n1,n1][1,1],[n,n],[2,2],[n-1,n-1]\cdots 效率明显低下。怎么办呢?离线做法,先对询问进行排序!

排序的伪代码:

结构体 Query {int l, r, id;}
比较(Query a, Query b):
    如果 a.l 与 b.l 在同一块中:
        比较 a.r 与 b.r 并返回
    否则:
        比较 a.l 与 b.l 并返回

在排序后,这个算法的效率是更高的,可以算出复杂度为 O(nn)O(n\sqrt{n})

(写作时间紧张,复杂度证明先咕了,改天再加)

例题 2:P2709 小B的询问

统计区间内不同数的个数的平方和,与上面类似,采用莫队。

//By: [email protected]_er(122461)
#include <bits/stdc++.h>
using namespace std;
const int N = 5e4+5, SIZE = 250;

int n, m, k, a[N], tot, s[N], ans[N];
#define whichBlock(x) (\
	(x-1)/SIZE+1\
)
struct Node {
	int l, r, id;
	friend bool operator < (const Node &a, const Node &b) { // 排序方法
		int x = whichBlock(a.l), y = whichBlock(b.l);
		if(x == y) return a.r < b.r;
		return x < y;
	}
}q[N];

void modify(int x, int y) { // 莫队指针移动更新数据
	int z = a[x];
	tot -= s[z] * s[z];
	s[z] += y;
	tot += s[z] * s[z];
}

int main() {
	scanf("%d%d%d", &n, &m, &k);
	for(int i=1;i<=n;i++) scanf("%d", &a[i]);
	for(int i=1;i<=m;i++) {
		scanf("%d%d", &q[i].l, &q[i].r);
		q[i].id = i;
	}
	sort(q+1, q+1+m);
	int l = 1, r = 0;
	for(int i=1;i<=m;i++) {
		while(l < q[i].l) modify(l++, -1); // 移动指针
		while(l > q[i].l) modify(--l, 1);
		while(r < q[i].r) modify(++r, 1);
		while(r > q[i].r) modify(r--, -1);
		ans[q[i].id] = tot;
	}
	for(int i=1;i<=m;i++) printf("%d\n", ans[i]);
	return 0;
}

习题 1:P1494 [国家集训队]小Z的袜子

小Z的妹子袜子这题需要一定的数学推导,和上面那题类似,也需要维护区间平方和。

习题 2:P4688 [Ynoi2016]掉进兔子洞 | 题解

用 bitset 套莫队即可。


完结撒花!

带修莫队和树上莫队因为自己还没做所以先不写了,以后会写新博客更新的~

(话说我这么用 Ynoi 当习题会不会被打)