暴力算法 --- 莫队

莫队

什么是莫队？

答：优雅的暴力！！！

基础莫队

重复的数

题目描述：给出一个长度为$N$的序列，有若干查询，每次查询区间$[l_i,r_i]$出现$k_i$次的数有多少个？

解题思路:最直观的做法就是拿到区间$[l,r]$后，暴力计算，用$cnt[x]$保存$x$出现了几个，$pos[t]$出现$t$次的数有几个。此时，时间复杂度最坏为：$\mathcal{O}(n^2)$
可以尝试来优化一下这个操作:使用两个指针$L$和$R$（初始化：$L=1,R=0$）,对于每次查询，依次的把这两个指针移动到目标区间$[l,r]$的同时，更新$cnt$和$pos$数组。假设现在目标区间为：$[1,5]$，$L=2,R=5$；移动$L$指针左移L--，并更新$cnt$和$pos$数组：

L --;
pos[cnt[a[L]]] --;
cnt[a[L]] ++;
pos[cnt[a[L]]] ++;
1
2
3
4

移完以后，同理移动$R$指针：

R ++;
pos[cnt[a[R]]] --;
cnt[a[R]] ++;
pos[cnt[a[R]]] ++;
1
2
3
4

可以发现上述都是把不在指针区间$[L,R]$的数加进来了，因此可以封装成一个函数：

void add(int x) { // 把一个数x加入当指针区间内
    pos[cnt[x]] --;
    cnt[x] ++;
    pos[cnt[x]] ++;
}
1
2
3
4
5

有增加就有删除，删除也是一样的：

void del(int x) { // 把一个数从指针区间删除
    pos[cnt[x]] --;
    cnt[x] --;
    pos[cnt[x]] ++;
}
1
2
3
4
5

为了减少$[L,R]$这两个指针的移动次数，可以先将序列分成$\sqrt{n}$块，并从$1\sim \sqrt{n}$编号，对于所有的查询按照块编号，从小到大排序，对于同一块，按照区间右端点升序排序。排完序后，我们再按照上述的操作去移动$L,R$指针，这样的时间复杂度为：$\mathcal{O}(n\sqrt{n})$

简单证明一下：

1. 区间排序，sort一遍，$\mathcal{O}(nlogn)$
2. $L$指针的移动：对于每块最坏跨越整个块$\sqrt{n}$,最坏有$n$块需要移动，总的：$\mathcal{O}(n\sqrt{n})$
3. $R$指针的移动，因为对于每块，区间是按照右端点升序排序，所以在块内最多也移动$\sqrt{n}$，最坏有$n$块需要移动，总的$\mathcal{O}(n\sqrt{n})$

综上述：莫队的总时间复杂度为： $\mathcal{O}(nlogn)+\mathcal{O}(n\sqrt{n})+\mathcal{O}(n\sqrt{n})=\mathcal{O}(n\sqrt{n})$

AC_Code:

#include 
using namespace std;
constexpr int N = 1e5 + 10;
int n, len, m, a[N], cnt[N], pos[N];
int bel(int x) {
	return x / len;
}
struct query {
	int l, r, k, id;
	bool operator < (const query &b){
		return bel(l) == bel(b.l) ? r < b.r : bel(l) < bel(b.l);
	}
};

void add(int x) {
	pos[cnt[x]] --; 
	cnt[x] ++;
	pos[cnt[x]] ++;
}

void del(int x) {
	pos[cnt[x]] --;
	cnt[x] --;
	pos[cnt[x]] ++;
}

int main() {
	scanf("%d", &n); len = sqrt(n);
	for (int i = 1; i <= n; i ++) scanf("%d", &a[i]);
	scanf("%d", &m);
	vector<query> q(m);
	vector<int> ans(m);
	for (int i = 0; i < m; i ++) {
		q[i].id = i;
		cin >> q[i].l >> q[i].r >> q[i].k;
	}
	sort(q.begin(), q.end());
	for (int i = 0, l = 1, r = 0; i < m; i ++) {
		int ql = q[i].l, qr = q[i].r;
		while (l > ql) add(a[-- l]);
		while (r < qr) add(a[++ r]);
		while (l < ql) del(a[l ++]);
		while (r > qr) del(a[r --]);
		ans[q[i].id] = pos[q[i].k];
	}
	for (int i = 0; i < m; i ++) cout << ans[i] << "\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
34
35
36
37
38
39
40
41
42
43
44
45
46
47

带修改莫队

P1903 [国家集训队] 数颜色 / 维护队列

题目描述：有长度为$N$的序列，现在有两个操作：

1. $QLR$ 区间$[L,R]$有多少个不同的数
2. $RPC$ 把$P$位置的数改成$C$

解题思路:查询操作可以用莫队轻松解决，可是这个修改要怎么办呢？我们可以加上一维时间，使之变为待修改莫队！具体操作如下：

增加一维时间t，在把区间移动到目标区间后，检查当前时间是不是目标时间，不是的话，跟修改$L,R$指针一样去修改时间t。

这里要注意的是，比如你现在把某个位置的数$x$改成了$c$,此时的时间为$t_1$,在把$x$修改为$c$后，这个时候你要把原来的数$x$记下来，如果以后询问小于$t_1$的时候，这个位置的数是$x$而不是$c$，这里有个简化操作，可以直接把$x$和$c$互换即可，下次操作直接更改就行（具体细节看代码

AC_Code：

#include 
using namespace std;

constexpr int N = 1e6 + 10;
int n, m, len, a[N], cnt[N];

int bel(int x) {
	return x / len;
}

struct query {
	int l, r, t, id;
	bool operator < (const query & b) {
		return (bel(l) ^ bel(b.l)) ? bel(l) < bel(b.l) : 
									(bel(r) ^ bel(b.r)) ? bel(r) < bel(b.r) : t < b.t; 
	}
};
struct M {
	int pos, color;
};

M modify[N];
int now;
void add(int x) {
	if(!cnt[x]) ++ now;
	cnt[x] ++;
}
void del(int x) {
	cnt[x] --;
	if(!cnt[x]) -- now;
}
int main() {
	scanf("%d%d", &n, &m); 
	//len = sqrt(n); 此时退化为了O(n^2)
	len = pow(n, 2.0 / 3);
	for (int i = 1; i <= n; i ++) scanf("%d", &a[i]);
	vector<query> q; int cntc = 0;
	for (int i = 0; i < m; i ++) {
		char opt[2]; int l, r;
		scanf("%s%d%d", opt, &l, &r);
		if(opt[0] == 'Q') {
			q.push_back({l, r, cntc, (int)q.size()});
		} else {
			modify[++cntc] = {l, r};
		}
	}
	sort(q.begin(), q.end());
	vector<int> ans(q.size());
	for (int i = 0, l = 1, r = 0, t = 0; i < (int)q.size(); i ++) {
		int ql = q[i].l, qr = q[i].r, qt = q[i].t;
		while (l > ql) add(a[-- l]);
		while (r < qr) add(a[++ r]);
		while (l < ql) del(a[l ++]);
		while (r > qr) del(a[r --]);
		while (t < qt) {
			++ t;
			if(ql <= modify[t].pos && qr >= modify[t].pos) {
				del(a[modify[t].pos]);
				add(modify[t].color);
			}
			swap(a[modify[t].pos], modify[t].color);
		}
		while (t > qt) {
			if(ql <= modify[t].pos && qr >= modify[t].pos) {
				del(a[modify[t].pos]);
				add(modify[t].color);
			}
			swap(a[modify[t].pos], modify[t].color);
			-- t;
		}
		ans[q[i].id] = now;
	}
	for (int &x : ans) cout << x << "\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
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

树上莫队

COT2 - Count on a tree II

题目描述：给定$N$个节点的树，每个节点有一个颜色。现在有$m$次询问，每次询问给出两个节点$u,v$，输出$u,v$路径上的节点颜色个数。颜色为$\le 2\times 10^9$的非负整数

解题思路：

先得到树的欧拉序。

欧拉序特点：

每个节点出现两次，且他们中间的节点为这个节点子树上的点

欧拉序的求法：

在dfs的时候，得到一个点加入序列，退出的时候也加入序列，这样就得到了欧拉序

得到欧拉序有什么用呢，可以尝试将两个节点映射成欧拉序上的一段区间，这样问题就可以转换为莫队求区间不同数了。

看上图，1->3很容易得到（就是图中红线）而且之间出现两次的数刚好不会算在其中。但是4->3怎么算？用第一个4指定不行，只能用第二个4，但是我们发现少了1，但是1是什么呢，是4和3的lca！所以，可以得到下面两个结论！(保证$first[x]<first[y]$，不满足就交换一下)

1. 如果$LCA(x,y)==x$，区间为$[first[x],first[y]$ 对应上图1->3情况
2. 如果$LCA(x,y)!=x$，区间为$[second[x],first[y]]$，同时标记lca为$LCA(x,y)$，在计算的时候加上lca

AC_Code：

#include 
using namespace std;
template < typename T>
inline void read( T &x)
{
    x = 0; bool f = 0;
    char ch = getchar();
    while(!isdigit(ch)) { f ^= !(ch ^ 45), ch = getchar();}
    while(isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
    x = f ? -x : x;
}
template < typename T>
inline void write(T x)
{
    if(x < 0) putchar('-'), x = -x;
    if(x > 9) write(x / 10);
    putchar(x % 10 + 48);
}
template <typename T>
inline void write(T x, char ch) {
	write(x);
	putchar(ch);
}
constexpr int N = 2e5 + 10;
int n, m, len, a[N], cnt[N], ord[N], first[N], last[N], ncnt, depth[N], fa[N][30];
vector<int> G[N];

int bel(int x) {
	return x / len;
}

struct query {
	int l, r, lca, id;
	bool operator < (const query & b) {
		return (bel(l) ^ bel(b.l)) ? bel(l) < bel(b.l) : r < b.r;
	}
};

void dfs(int u) {
	ord[++ ncnt] = u;
	first[u] = ncnt;
	for (int &x : G[u]) {
		if(x == fa[u][0]) continue;
		depth[x] = depth[u] + 1;
		fa[x][0] = u;
		for (int i = 1; (1 << i) <= depth[x]; i ++)
			fa[x][i] = fa[fa[x][i - 1]][i - 1];
		dfs(x);
	}
	ord[++ ncnt] = u;
	last[u] = ncnt;
}

int LCA(int u, int v) {
	if(depth[u] < depth[v]) swap(u, v);
	for (int i = 20; i + 1;i --)
		if(depth[u] - (1 << i) >= depth[v]) u = fa[u][i];
	if(u == v) return u;
	for (int i = 20; i + 1; i --) 
		if(fa[u][i] != fa[v][i])
			u = fa[u][i], v = fa[v][i];
	return fa[u][0];
}

int vis[N], now;
vector<int> all;

void solve(int pos) {
	if(vis[pos]) {
		cnt[a[pos]] --;
		if(!cnt[a[pos]]) now --;
	} else {
		if(!cnt[a[pos]]) now ++;
		cnt[a[pos]] ++;
	}
	vis[pos] ^= 1;
}

int main() {
	read(n); read(m);
	for (int i = 1; i <= n; i ++)
		read(a[i]), all.push_back(a[i]);
	sort(all.begin(), all.end());
	all.erase(unique(all.begin(), all.end()), all.end());
	for (int i = 1; i <= n; i ++)
		a[i] = lower_bound(all.begin(), all.end(), a[i]) - all.begin() + 1;
	for (int i = 1; i < n; i ++) {
		int u, v;
		read(u); read(v);
		G[u].push_back(v); G[v].push_back(u);
	}
	depth[1] = 1;
	dfs(1);
	len = sqrt(ncnt);
	vector<query> q(m);
	for (int i = 0; i < m; i ++) {
		int l, r;
		read(l); read(r);
		int lca = LCA(l, r);
		if(first[l] > first[r]) swap(l, r);
		if(l == lca) {
			q[i].l = first[l];
			q[i].r = first[r];
		} else {
			q[i].l = last[l];
			q[i].r = first[r];
			q[i].lca = lca;
		}
		q[i].id = i;
	}
	sort(q.begin(), q.end());
	vector<int>ans(m);
	for (int i = 0, l = 1, r = 0; i < m; i ++) {
		int ql = q[i].l, qr = q[i].r, lca = q[i].lca;
		while (l > ql) solve(ord[-- l]);
		while (r < qr) solve(ord[++ r]);
		while (l < ql) solve(ord[l ++]);
		while (r > qr) solve(ord[r --]);
		if(lca) solve(lca);
		ans[q[i].id] = now;
		if(lca) solve(lca);
	}
	for (int &x : ans) write(x, '\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
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
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124

回滚莫队

// TODO 待补
1

例题：

ABC293_G

题目链接：点我
题意：有一个长度为$N$的序列，现在有$m$次询问，每次询问一段区间内$(i<j<k)$并且$a_i=a_j=a_k$的对数
sol：利用莫队，往区间加数$X$的时候，对答案增加$cnt[x]\ast (cnt[x]-1)/2$，当前这一个和已有的匹配，删除同理

Code:

#include 
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
template < typename T> inline void Max(T &a, T b) { if(a < b) a = b; }
template < typename T> inline void Min(T &a, T b) { if(a > b) a = b; }
 
const int N = 2e5 + 10, B = 450;

struct Q {
	int l, r, id;
	bool operator < (const Q &b) const {
		if(l / B == b.l / B) return r < b.r;
		return l < b.l;
	}
}q[N];

int n, m;
int a[N];
LL c, ans[N], cnt[N];

void add(int x) {
	c += (cnt[a[x]] * (cnt[a[x]] - 1)) / 2;
	cnt[a[x]] ++;
}

void del(int x) {
	cnt[a[x]] --;
	c -= (cnt[a[x]] * (cnt[a[x]] - 1)) / 2;
}

int main() {
	
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	
	cin >> n >> m;

	for (int i = 1; i <= n;i ++) {
		cin >> a[i];
	}

	for (int i = 1; i <= m; i ++) {
		cin >> q[i].l >> q[i].r;
		q[i].id = i;
	}

	sort(q + 1, q + 1 + m);

	for (int i = 1, l = 1, r = 0; i <= m; i ++) {
		while (l > q[i].l) add(-- l);
		while (r < q[i].r) add(++ r);
		while (l < q[i].l) del(l ++);
		while (r > q[i].r) del(r --);
		ans[q[i].id] = c;
	}

	for (int i = 1;i <= m; i ++)
		cout << ans[i] << "\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
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