不讲道理算法

Posted on | In | | Visitors:
Words count in article: 2.3k | Reading time ≈ 10

90f43312d3678823f6c54b91f5a86498.jpeg

个人觉得分块和莫队都是相当暴力不讲道理的算法

分块

首先来说说分块。
顾名思义，把一段区间分成一块一块的。
分成一块块的有什么好处呢？如果我们要进行区间修改区间查询，当这个区间中包含了整个块时，如果我们知道了这个块的一些信息，就没必要对块内的元素一个个进行修改或查询，如此就达到了降低复杂度的目的。
于是分块的策略就很清楚了，对于当前操作的区间[L,R]，对于其中的整块我们整体修改或查询，而两边可能有的非整块元素则暴力修改，再将两端所属的块更新，这些元素个数显然不会超过两个块的大小，所以时间复杂度就有了保证。
那么块的大小应该怎么确定呢？理论上，如果区间长度为$n$，则当块大小为$\sqrt{n}$时时间复杂度是最优的，每次操作复杂度为$O(\sqrt{n})$。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
//以区间加和区间求和为例
void update(int l, int r, ll data) {
	if (bel[l] == bel[r]) {
		for (int i = l; i <= r; ++i)
			a[i] += data;
		block[bel[l]].sum += (r - l + 1) * data;
		return;
	}//同一块直接改
	for (int i = l; i <= bel[l] * nbl; ++i)
		a[i] += data;//左边角
	block[bel[l]].sum += (bel[l] * nbl - l + 1) * data;
	for (int i = bel[l] + 1; i < bel[r]; ++i)
		block[i].sum += nbl * data, block[i].del += data;//中间整块
	for (int i = (bel[r] - 1) * nbl + 1; i <= r; ++i)
		a[i] += data;//右边角
	block[bel[r]].sum += (r - (bel[r] - 1) * nbl) * data;
}
//查询也类同
ll query(int l, int r) {
	ll ans = 0;
	if (bel[l] == bel[r]) {
		for (int i = l; i <= r; ++i)
			ans += a[i] + block[bel[i]].del;
		return ans;
	}
	for (int i = l; i <= bel[l] * nbl; ++i)
		ans += a[i] + block[bel[i]].del;
	for (int i = bel[l] + 1; i < bel[r]; ++i)
		ans += block[i].sum;
	for (int i = (bel[r] - 1) * nbl + 1; i <= r; ++i)
		ans += a[i] + block[bel[i]].del;
	return ans;
}

莫队

莫队是在分块的基础上，更暴力的一种算法。
对于只有查询的题目，我们可以通过移动l r指针，计算相应的添加或者删除某个元素得到的贡献来得到所有查询的答案，但是这样的话复杂度可能达到$n^2$。
由于只有查询，我们可以将这些要查询的区间改变顺序，使得两个指针移动的距离尽量减少，从而达到降低复杂度的目的。
考虑将整个区间分块，然后将所有查询进行双关键字排序，第一关键字为左端点所在的块，第二关键字为右端点本身。
这样的话，对于左端点，在同一块内的转移每次不会超过$\sqrt{n}$，不同块之间的转移不会超过$\sqrt{n}$；
对于右端点，在左端点在同一块时，右端点是单调不降的，即最多$n$，而在左端点不同块之间的转移不会超过$\sqrt{n}$
因此总时间复杂度为$O(n\sqrt{n})$。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
struct Query {
	int l, r, id;
	Query() {}
	Query(int r, int l, int id): l(l), r(r), id(id) {}
	bool operator <(const Query s)const { return bel[l] < bel[s.l] || (bel[l] == bel[s.l] && r < s.r); }
}q[N];//双关键字排序
void ins(int x) {
	...
    //此处对新加进来的元素计算贡献
}
void del(int x) {
	...
    //此处删去某个元素的贡献
}
int main() {
    ...
	for (int i = 1; i <= n; ++i)bel[i] = (i - 1) / *bel + 1;
    ...
    sort(q + 1, q + m + 1);
	int l = 1, r = 0;
	for (int i = 1; i <= m; ++i) {
		while (r < q[i].r)ins(++r);
		while (l > q[i].l)ins(--l);
		while (r > q[i].r)del(r--);
		while (l < q[i].l)del(l++);
        //直接移动l r指针计算贡献
		ANS[q[i].id] = ans;//记录答案
	}
	for (int i = 1; i <= m; ++i)
		printf("%lld\n", ANS[i]);
    return 0;
}

带修莫队

带修莫队实际上就是在普通莫队的基础上增加一个时间轴，来表示修改的时间点。
分块策略与普通莫队类似，还是先l r分块，然后还要对同一块内的修改排序(假设为单点修改)
在移动完l r指针后，再去移动时间轴指针t，类似地进行相应修改，基本思想其实是一致的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
struct Node {
    int l, r, pre, bh;
    inline bool operator <(register Node s)const {
        if (blo[s.l] ^ blo[l])return s.l < l;
        if (blo[s.r] ^ blo[r]) return s.r < r;
        return s.pre < pre;
    }
    //此处pre记录时间戳，即当前查询在第几次修改后
}q[N];
...
int main() {
    ...
    for (int i = 1; i <= m; ++i) {
		while (r < q[i].r)ins(++r);
		while (l > q[i].l)ins(--l);
		while (r > q[i].r)del(r--);
		while (l < q[i].l)del(l++);
        while (now < q[i].pre)change(++now);
        while (now > q[i].pre)change(now--);
        //除了l r指针外还有now指针
        ans[q[i].bh] = sum;
    }
    ...
}

树上莫队

树上莫队用于解决树上问题，我们将树上问题转化为序列问题，从而使用莫队求解。
如何将一个树上的问题转化成一个序列问题呢？我们借助dfs序（括号序列）达到这一点。
首先指定根，对于每个点x，我们记录其在dfs过程中第一次遇到时dfs序为st[x]，第二次遇到时dfs序为ed[x]，并记录这两个dfs序对应的点euler[st[x]]=euler[ed[x]]=x。不难发现，在dfs序组成的长度为2n的序列中，如果在某一段区间[l,r]内st[x]和ed[x]同时存在，那么x必然不在原树上euler[l]和euler[r]的最短路径中，且为其中某个节点的后代。由此我们就能联想到，记录当前区间x是否出现过，进行相应的加或减操作，就可以统计出路径上的真实情况，形象地理解的话考虑从一个点到另一个点的过程中，先走到了中间某个点的其他分支，再走回来，走过去的过程中我们将中间的点都计入贡献，而回来时再将其删掉，这样就保证了正确性。
当然，上面给出的是一个相当模糊的概述，如果我们模拟一下就会发现，要分两种情况(设查询的点对为(x, y)，其中st[x] < st[y])：

  • LCA(x, y)为x，这时候只需要从ed[x]走到st[y]就可以了，从st[x]开始没有意义
  • LCA(x, y)不为x，这时候要注意，我们的区间[st[x], st[y]]中显然是不包括LCA的(为什么)，所以对于这个查询，我们还要记录下其LCA，在计算答案时将LCA计入答案，但是要记住，计入答案后要立刻删掉，不能影响到后面的答案计算，因为区间内实际上是没有LCA这个点的dfs序的。

下面给出树上数颜色的模板
洛谷SP10707 COT2 - Count on a tree II

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
struct Query {
	int l, r, lca, id;
	Query() {}
	Query(int l, int r, int lca, int id): l(l), r(r), lca(lca), id(id) {}
	bool operator <(const Query s)const { return block[l] < block[s.l] || (block[l] == block[s.l] && r < s.r); }
}q[N];
void add(int x, int y) {
	b[++num] = y, nt[num] = p[x], p[x] = num;
	b[++num] = x, nt[num] = p[y], p[y] = num;
}
void dfs1(int x) {
	sz[x] = 1;
	for (int e = p[x]; e; e = nt[e]) {
		int k = b[e];
		if (k == fa[x])continue;
		fa[k] = x;
		dep[k] = dep[x] + 1;
		dfs1(k);
		if (sz[son[x]] < sz[k])son[x] = k;
		sz[x] += sz[k];
	}
}
void dfs2(int x, int chain_number) {
	st[x] = ++tot;
	euler[tot] = x;
	bel[x] = chain_number;
	if (son[x])dfs2(son[x], chain_number);
	for (int e = p[x]; e; e = nt[e]) {
		int k = b[e];
		if (k == fa[x] || k == son[x])continue;
		dfs2(k, k);
	}
	ed[x] = ++tot;
	euler[tot] = x;
}
int LCA(int x, int y) {
	while (bel[x] != bel[y]) {
		if (dep[bel[x]] < dep[bel[y]])jh(x, y);
		x = fa[bel[x]];
	}
	if (dep[x] < dep[y])return x;
	return y;
}
void del(int x) { if (!--cnt[c[x]])--ans; }
void opt(int x) {
	if (use[x])del(x);
	else if (!(cnt[c[x]]++))++ans;
	use[x] ^= 1;
}

int main(void) {
	int n = fast_IO::read(), m = fast_IO::read();
	*block = sqrt(n << 1);
	for (int i = 1; i <= (n << 1); ++i)block[i] = (i - 1) / *block + 1;
	for (int i = 1; i <= n; ++i)c[i] = Hash[i] = fast_IO::read();
	for (int i = 1; i < n; ++i)add(fast_IO::read(), fast_IO::read());
	sort(Hash + 1, Hash + n + 1);
	*Hash = unique(Hash + 1, Hash + n + 1) - Hash - 1;
	for (int i = 1; i <= n; ++i)
		c[i] = lower_bound(Hash + 1, Hash + *Hash + 1, c[i]) - Hash;
	dfs1(1);
	dfs2(1, 1);
	for (int i = 1; i <= m; ++i) {
		int x = fast_IO::read(), y = fast_IO::read(), lca = LCA(x, y);
		if (st[x] > st[y])jh(x, y);
		if (lca == x)q[i] = Query(st[x], st[y], 0, i);
		else q[i] = Query(ed[x], st[y], lca, i);
	}
	sort(q + 1, q + m + 1);
	int l = 1, r = 0;
	for (int i = 1; i <= m; ++i) {
		while (r < q[i].r)opt(euler[++r]);
		while (l > q[i].l)opt(euler[--l]);
		while (r > q[i].r)opt(euler[r--]);
		while (l < q[i].l)opt(euler[l++]);
		if (q[i].lca)opt(q[i].lca);
		ANS[q[i].id] = ans;
		if (q[i].lca)opt(q[i].lca);
	}
	for (int i = 1; i <= m; ++i)
		printf("%d\n", ANS[i]);
	return 0;
}

回滚莫队

咕咕咕