莫队入门题（模板用）

普通莫队

黑暗爆炸 - 2038 小Z的袜子(hose)

查询区间中任意取两数相等的概率

1	#include <iostream>
2	#include <cstdio>
3	#include <cmath>
4	#include <algorithm>
5	using namespace std;
6	const int N = 1E5 + 7;
7	int c[N], pos[N];
8	struct QRY{
9	int l, r, id;
10	bool operator < (const QRY &tmp)const{
11	return pos[l] == pos[tmp.l]?r < tmp.r:l < tmp.l;
12	}
13	}q[N];
14	struct ANS{
15	long long a, b;
16	}ans[N];
17	long long gcd(long long a, long long b){
18	return b == 0?a:gcd(b, a % b);
19	}
20	long long cnt[N];
21	long long sum = 0;
22	void add(int x){
23	sum += cnt[x];
24	cnt[x]++;
25	}
26	void del(int x){
27	cnt[x]--;
28	sum -= cnt[x];
29	}
30	int main(){
31	int n, m, l, r;
32	scanf("%d%d", &n, &m);
33	int t = sqrt(n);
34	for(int i = 1; i <= n; i++){
35	scanf("%d", &c[i]);
36	pos[i] = i / t + 1;
37	}
38	for(int i = 1; i <= m; i++){
39	scanf("%d%d", &l, &r);
40	ans[i].b = 1;
41	q[i] = {l, r, i};
42	}
43	sort(q + 1, q + m + 1);
44	l = 1, r = 0;
45	for(int i = 1; i <= m; i++){
46	if(q[i].l == q[i].r) continue;
47	while(l > q[i].l) add(c[--l]);
48	while(r < q[i].r) add(c[++r]);
49	while(l < q[i].l) del(c[l++]);
50	while(r > q[i].r) del(c[r--]);
51	ans[q[i].id] = {sum, (long long)(q[i].r - q[i].l + 1) * (q[i].r - q[i].l) / 2};
52	long long g = gcd(ans[q[i].id].a, ans[q[i].id].b);
53	ans[q[i].id].a /= g; ans[q[i].id].b /= g;
54	}
55	for(int i = 1; i <= m; i++) printf("%lld/%lld\n", ans[i].a, ans[i].b);
56	return 0;
57	}

莫队+数据结构

BZOJ3809 Gty的二逼妹子序列

查询区间内值在[a, b]范围内的种类数，可用莫队+树状数组维护

1	#include <iostream>
2	#include <cstdio>
3	#include <cmath>
4	#include <algorithm>
5	using namespace std;
6	const int N = 3E5 + 7;
7	int s[N], pos[N];
8	struct QRY{
9	int l, r, a, b, id;
10	bool operator < (const QRY &tmp) const{
11	return pos[l] == pos[tmp.l]?r < tmp.r:l < tmp.l;
12	}
13	}q[N * 4];
14	int hv[N], block[N];
15	int ans[N * 4];
16	void add(int x){
17	if(!hv[x]) block[pos[x]]++;
18	hv[x]++;
19	}
20	void del(int x){
21	hv[x]--;
22	if(!hv[x]) block[pos[x]]--;
23	}
24	int main(){
25	int n, m, l, r, a, b;
26	scanf("%d%d", &n, &m);
27	int t = sqrt(n);
28	for(int i = 1; i <= n; i++){
29	scanf("%d", &s[i]);
30	pos[i] = i / t + 1;
31	}
32	for(int i = 1; i <= m; i++){
33	scanf("%d%d%d%d", &l, &r, &a, &b);
34	q[i] = {l, r, a, b, i};
35	}
36	sort(q + 1, q + m + 1);
37	l = 0, r = 0;
38	for(int i = 1; i <= m; i++){
39	while(l > q[i].l) add(s[--l]);
40	while(r < q[i].r) add(s[++r]);
41	while(l < q[i].l) del(s[l++]);
42	while(r > q[i].r) del(s[r--]);
43	a = q[i].a; b = q[i].b;
44	int res = 0;
45	if(pos[a] == pos[b]){
46	while(a <= b){
47	if(hv[a]) res++;
48	a++;
49	}
50	ans[q[i].id] = res;
51	continue;
52	}
53	int x = pos[a] * t, y = (pos[b] - 1) * t;
54	while(a < x && a <= n){
55	if(hv[a]) res++;
56	a++;
57	}
58	while(y <= b){
59	if(hv[y]) res++;
60	y++;
61	}
62	for(int j = pos[q[i].a] + 1; j < pos[q[i].b]; j++){
63	res += block[j];
64	}
65	ans[q[i].id] = res;
66	}
67	for(int i = 1; i <= m; i++){
68	printf("%d\n", ans[i]);
69	}
70	}

带修莫队

CodeForces - 940F Machine Learning

查询区间数出现次数的MEX（因答案不超过1000，故可以每次暴力查询）

1	#include <iostream>
2	#include <cstdio>
3	#include <algorithm>
4	#include <cmath>
5	#include <unordered_map>
6	using namespace std;
7	const int N = 2e5 + 7;
8	int pos[N], a[N];
9	int chp[N], chx[N];
10	int hv[N], ct[N];
11	struct QRY{
12	int l, r, t, id;
13	bool operator < (const QRY &tmp)const{
14	if(pos[l] != pos[tmp.l]) return l < tmp.l;
15	if(pos[r] != pos[tmp.r]) return r < tmp.r;
16	return t < tmp.t;
17	}
18	}q[N];
19	int cnt, tt, tot;
20	unordered_map<int, int> ma;
21	int res = 1;
22	int l, r;
23	int ans[N];
24	void add(int x){
25	int tmp = ct[x]++;
26	hv[tmp]--;
27	hv[tmp + 1]++;
28	}
29	void del(int x){
30	int tmp = ct[x]--;
31	hv[tmp]--;
32	hv[tmp - 1]++;
33	}
34	void work(int x){
35	if(l <= chp[x] && chp[x] <= r){
36	del(a[chp[x]]);
37	add(chx[x]);
38	}
39	swap(a[chp[x]], chx[x]);
40	}
41	int main(){
42	int n, m, t = 0, opt, rr;
43	scanf("%d%d", &n, &m);
44	int block_size = pow(n, 2.0 / 3);
45	for(int i = 1; i <= n; i++){
46	scanf("%d", &rr);
47	if(ma[rr]) a[i] = ma[rr];
48	else{
49	a[i] = ++tot;
50	ma[rr] = tot;
51	}
52	pos[i] = i / block_size + 1;
53	}
54	for(int i = 1; i <= m; i++){
55	scanf("%d%d%d", &opt, &l, &r);
56	if(opt == 1){
57	cnt++;
58	q[cnt] = {l, r, tt, cnt};
59	}
60	else{
61	tt++;
62	chp[tt] = l;
63	if(ma[r]) chx[tt] = ma[r];
64	else{
65	ma[r] = ++tot;
66	chx[tt] = tot;
67	}
68	}
69	}
70	sort(q + 1, q + cnt + 1);
71	l = r = t = 0;
72	hv[0] = 1e9;
73	for(int i = 1; i <= cnt; i++){
74	while(l > q[i].l) add(a[--l]);
75	while(r < q[i].r) add(a[++r]);
76	while(l < q[i].l) del(a[l++]);
77	while(r > q[i].r) del(a[r--]);
78	while(t < q[i].t) work(++t);
79	while(t > q[i].t) work(t--);
80	res = 1;
81	while(hv[res]) res++;
82	ans[q[i].id] = res;
83	}
84	for(int i = 1; i <= cnt; i++) printf("%d\n", ans[i]);
85	}

回滚莫队

只使用增加操作

AT1219 歴史の研究

求区间 $\max\{v * cnt_v\}$ 。

1	#include <iostream>
2	#include <cstdio>
3	#include <cmath>
4	#include <algorithm>
5	using namespace std;
6	const int N = 2E5 + 7;
7	long long a[N], b[N];
8	int pos[N], block;
9	struct QRY{
10	int l, r, id;
11	bool operator<(const QRY &_)const{
12	if(pos[l] != pos[_.l]) return l < _.l;
13	return r < _.r;
14	}
15	}qry[N];
16	long long ans[N];
17	int cnt[N], tcnt[N];
18	void add(int x, long long &v){
19	cnt[a[x]]++;
20	v = max(v, cnt[a[x]] * b[a[x]]);
21	}
22	void del(int x){
23	cnt[a[x]]--;
24	}
25	int main(){
26	int n, q, l, r;
27	scanf("%d%d", &n, &q);
28	block = sqrt(n);
29	for(int i = 1; i <= n; i++){
30	scanf("%lld", &a[i]);
31	b[i] = a[i];
32	pos[i] = (i - 1) / block + 1;
33	}
34	sort(b + 1, b + n + 1);
35	int nk = unique(b + 1, b + n + 1) - b - 1;
36	for(int i = 1; i <= n; i++) a[i] = lower_bound(b + 1, b + nk + 1, a[i]) - b;
37	for(int i = 1; i <= q; i++){
38	scanf("%d%d", &l , &r);
39	qry[i] = {l, r, i};
40	}
41	sort(qry + 1, qry + q + 1);
42	long long res = 0;
43	l = 1; r = 0; int nb = 0;
44	for(int i = 1; i <= q; i++){
45	if(pos[qry[i].l] == pos[qry[i].r]){
46	long long tmp = 0;
47	for(int j = qry[i].l; j <= qry[i].r; j++){
48	tcnt[a[j]]++;
49	tmp = max(tmp, tcnt[a[j]] * b[a[j]]);
50	}
51	ans[qry[i].id] = tmp;
52	for(int j = qry[i].l; j <= qry[i].r; j++) tcnt[a[j]]--;
53	continue;
54	}
55	if(pos[qry[i].l] != nb){
56	int tl = min(n + 1, pos[qry[i].l] * block + 1);
57	int tr = l - 1;
58	while(l < tl) del(l++);
59	while(r > tr) del(r--);
60	res = 0;
61	nb = pos[qry[i].l];
62	}
63	while(r < qry[i].r) add(++r, res);
64	int ll = l; long long tmp = res;
65	while(ll > qry[i].l) add(--ll, tmp);
66	ans[qry[i].id] = tmp;
67	while(ll < l) del(ll++);
68	}
69	for(int i = 1; i <= q; i++) printf("%lld\n", ans[i]);
70	return 0;
71	}

用栈记录历史修改的写法

给一个序列 $A$，$q$ 次询问，每次询问给一个区间 $[L,R]$，再给一个 $k$，要求

$\sum_{i = 0}^{k - 1}{f(\{A_{l-i}\dots A_{r + i}\}) \times (n + i)^i (\mod P)} \\ f(S)=\max\{len|\exist x,\forall u \in \{x,x + 1,\dots,x + len - 1\}, u \in S\}$

1	#include <iostream>
2	#include <cstdio>
3	#include <cmath>
4	#include <algorithm>
5	#include <stack>
6	using namespace std;
7	const long long mod = 998244353;
8	const int N = 1E5 + 7;
9	int block;
10	int a[N], cnt[N], pos[N];
11	struct QRY{
12	int l, r, k, id;
13	bool operator < (const QRY &_)const{
14	if(pos[l] != pos[_.l]) return l < _.l;
15	return r < _.r;
16	}
17	}q[N];
18	int head[N], tail[N];
19	long long pw[N];
20	stack<pair<int* , int>> st;
21	void clear(int sz){
22	while(st.size() > sz){
23	*st.top().first = st.top().second;
24	st.pop();
25	}
26	}
27	void upd(int* v, int x){
28	st.push({v, *v});
29	*v = x;
30	}
31	int res;
32	void add(int x){
33	x = a[x];
34	if(cnt[x]) return;
35	upd(&cnt[x], 1);
36	int r = cnt[x + 1] ? tail[x + 1] : x, l = cnt[x - 1] ? head[x - 1] : x;
37	upd(&head[r], l); upd(&tail[l], r);
38	if(r - l + 1 > res) upd(&res, r - l + 1);
39	}
40	long long ans[N];
41	int main(){
42	int n, qq;
43	scanf("%d%d", &n, &qq);
44	block = sqrt(n);
45	for(int i = 1; i <= n; i++){
46	scanf("%d", &a[i]);
47	pos[i] = (i - 1) / block + 1;
48	}
49	pw[0] = 1;
50	for(int i = 1; i <= n; i++) pw[i] = pw[i - 1] * (n + 1) % mod;
51	int l, r, k;
52	for(int i = 1; i <= qq; i++){
53	scanf("%d%d%d", &l, &r, &k);
54	q[i] = {l, r, k, i};
55	}
56	sort(q + 1, q + qq + 1);
57	l = r = 0; int lb = 0;
58	for(auto sq: q){
59	if(pos[sq.l] != lb){
60	r = min(pos[sq.l] * block, n);
61	l = r + 1;
62	lb = pos[sq.l];
63	clear(0);
64	}
65	while(r < sq.r) add(++r);
66	int ts = st.size();
67	for(int j = min(sq.r, l - 1); j >= sq.l; j--) add(j);
68	for(int j = 0; j < sq.k; j++){
69	if(j) add(sq.l - j), add(sq.r + j);
70	ans[sq.id] = (ans[sq.id] + res * pw[j]) % mod;
71	}
72	clear(ts);
73	}
74	for(int i = 1; i <= qq; i++) printf("%lld\n", ans[i]);
75	return 0;
76	}

树上莫队

Luogu-P4074 糖果公园

给一棵$n$个节点的树，每个点有一个值$C_i$，每次询问一条路径 $ x \rightarrow y$，求$\sum_cval_c \times \sum_{i = 1}^{cnt_c}{worth_i}(cnt_c = \sum_{i \in (x \rightarrow y)}{[C_i ==c]})$。带修改。

树上问题转括号序列

1	#include <iostream>
2	#include <cstdio>
3	#include <vector>
4	#include <cmath>
5	#include <algorithm>
6	using namespace std;
7	const int N = 1e5 + 7;
8	int vc[N], w[N];
9	int id[N * 2], st[N], en[N],cnt;
10	int f[N][22], dep[N], lg[N];
11	int pos[N * 2];
12	long long ans[N];
13	int vis[N];
14	int c[N];
15	struct CHG{
16	int idx, val;
17	};
18	vector<vector<int> > e;
19	vector<CHG> ver;
20	void dfs(int x, int fa){
21	id[st[x] = ++cnt] = x;
22	dep[x] = dep[fa] + 1;
23	f[x][0] = fa;
24	for(int i = 1; i <= 20; i++) f[x][i] = f[f[x][i - 1]][i - 1];
25	for(auto v: e[x]){
26	if(v == fa) continue;
27	dfs(v, x);
28	}
29	id[en[x] = ++cnt] = x;
30	}
31	int lca(int x, int y){
32	if(dep[x] < dep[y]) swap(x, y);
33	while(dep[x] > dep[y]){
34	x = f[x][lg[dep[x] - dep[y]]];
35	}
36	if(x == y) return x;
37	for(int i = 20; i >= 0; i--){
38	if(f[x][i] != f[y][i]){
39	x = f[x][i]; y = f[y][i];
40	}
41	}
42	return f[x][0];
43	}
44	struct QRY{
45	int l, r, t, id;
46	bool operator<(const QRY &_)const{
47	if(pos[l] != pos[_.l]) return l < _.l;
48	if(pos[r] != pos[_.r]) return r < _.r;
49	return t < _.t;
50	}
51	};
52	vector<QRY> qry;
53	int tv = 0;
54	long long res = 0;
55	int ct[N];
56	void add(int x){
57	if(vis[x]) res -= (long long)vc[c[x]] * w[ct[c[x]]--];
58	else res += (long long)vc[c[x]] * w[++ct[c[x]]];
59	vis[x] ^= 1;
60	}
61	void work(int x){
62	if(vis[ver[x].idx]){
63	add(ver[x].idx);
64	swap(c[ver[x].idx], ver[x].val);
65	add(ver[x].idx);
66	}
67	else swap(c[ver[x].idx], ver[x].val);
68	}
69	int main(){
70	int n, m, q, x, y, opt;
71	scanf("%d%d%d", &n, &m, &q);
72	for(int i = 2; i <= n; i++) lg[i] = lg[i >> 1] + 1;
73	e.resize(n + 1);
74	for(int i = 1; i <= m; i++) scanf("%d", &vc[i]);
75	for(int i = 1; i <= n; i++) scanf("%d", &w[i]);
76	for(int i = 1; i < n; i++){
77	scanf("%d%d", &x, &y);
78	e[x].push_back(y);
79	e[y].push_back(x);
80	}
81	for(int i = 1; i <= n; i++) scanf("%d", &c[i]);
82	dfs(1, 0);
83	int blk = pow(cnt, 2.0 / 3);
84	for(int i = 1; i <= cnt; i++) pos[i] = i / blk + 1;
85	ver.push_back({0, 0});
86	for(int i = 1; i <= q; i++){
87	scanf("%d%d%d", &opt, &x, &y);
88	if(opt == 0){
89	tv++;
90	ver.push_back({x, y});
91	}
92	else{
93	if(st[x] > st[y]) swap(x, y);
94	qry.push_back({lca(x, y) == x?st[x]:en[x], st[y], tv, (int)qry.size()});
95	}
96	}
97	sort(qry.begin(), qry.end());
98	int l, r, t;
99	l = r = 0; t = 0;
100	for(auto sq: qry){
101	while(t < sq.t) work(++t);
102	while(t > sq.t) work(t--);
103	while(l > sq.l) add(id[--l]);
104	while(r < sq.r) add(id[++r]);
105	while(l < sq.l) add(id[l++]);
106	while(r > sq.r) add(id[r--]);
107	x = id[sq.l], y = id[sq.r];
108	int llca = lca(x, y);
109	if(x != llca && y != llca){
110	add(llca);
111	ans[sq.id] = res;
112	add(llca);
113	}
114	else ans[sq.id] = res;
115	}
116	for(int i = 0; i < qry.size(); i++) printf("%lld\n", ans[i]);
117	}

树上分块

1	#include <iostream>
2	#include <cstdio>
3	#include <vector>
4	#include <stack>
5	#include <cmath>
6	#include <algorithm>
7	using namespace std;
8	const int N = 1E5 + 7;
9	int val[N], w[N], c[N];
10
11	long long ans[N];
12	long long res;
13	vector<vector<int> > e;
14	stack<int> st;
15	int block_size, blk;
16	int dep[N], sze[N], bc[N], bl[N], f[N];
17	void dfs1(int x, int fa){
18	dep[x] = dep[fa] + 1;
19	f[x] = fa;
20	sze[x] = 1;
21	int ss = st.size();
22	for(auto v: e[x]){
23	if(v == fa) continue;
24	dfs1(v, x);
25	if(sze[bc[x]] < sze[v]) bc[x] = v;
26	sze[x] += sze[v];
27	if(st.size() >= ss + block_size){
28	blk++;
29	while(st.size() != ss){
30	bl[st.top()] = blk;
31	st.pop();
32	}
33	}
34	}
35	st.push(x);
36	}
37	int id[N], top[N], cnt;
38	void dfs2(int x, int rt){
39	id[x] = ++cnt;
40	top[x] = rt;
41	if(bc[x]) dfs2(bc[x], rt);
42	for(auto v: e[x]){
43	if(v == f[x] \|\| v == bc[x]) continue;
44	dfs2(v, v);
45	}
46	}
47	int lca(int x, int y){
48	while(top[x] != top[y]){
49	if(dep[top[x]] < dep[top[y]]) swap(x, y);
50	x = f[top[x]];
51	}
52	return dep[x] < dep[y] ? x : y;
53	}
54	struct VT{
55	int x, y;
56	};
57	vector<VT> ve;
58	struct QRY{
59	int x, y, t, id;
60	bool operator<(const QRY &r)const{
61	if(bl[x] != bl[r.x]) return bl[x] < bl[r.x];
62	if(bl[y] != bl[r.y]) return bl[y] < bl[r.y];
63	return t < r.t;
64	}
65	};
66	vector<QRY> qry;
67	bool vis[N];
68	int ct[N];
69	void update(int x){
70	if(vis[x]){
71	res -= (long long)w[ct[c[x]]--] * val[c[x]];
72	}
73	else{
74	res += (long long)w[++ct[c[x]]] * val[c[x]];
75	}
76	vis[x] ^= 1;
77	}
78	void move(int x, int y){
79	if(dep[x] < dep[y]) swap(x, y);
80	while(dep[x] > dep[y]){
81	update(x);
82	x = f[x];
83	}
84	while(x != y){
85	update(x);
86	update(y);
87	x = f[x];
88	y = f[y];
89	}
90	}
91	void make(int t){
92	if(vis[ve[t].x]){
93	update(ve[t].x);
94	swap(ve[t].y, c[ve[t].x]);
95	update(ve[t].x);
96	}
97	else swap(ve[t].y, c[ve[t].x]);
98	}
99	int main(){
100	int n, m, q, u, v;
101	scanf("%d%d%d", &n, &m, &q);
102	e.resize(n + 1);
103	block_size = (int)pow(n, 0.6);
104	for(int i = 1; i <= m; i++) scanf("%d", &val[i]);
105	for(int i = 1; i <= n; i++) scanf("%d", &w[i]);
106	for(int i = 1; i < n; i++){
107	scanf("%d%d", &u, &v);
108	e[u].push_back(v);
109	e[v].push_back(u);
110	}
111	for(int i = 1; i <= n; i++) scanf("%d", &c[i]);
112	dfs1(1, 1);
113	while(!st.empty()){
114	blk++;
115	bl[st.top()] = blk;
116	st.pop();
117	}
118	dfs2(1, 1);
119	int opt, x, y;
120	int ver = 0;
121	ve.push_back({0, 0});
122	for(int i = 1; i <= q; i++){
123	scanf("%d%d%d", &opt, &x, &y);
124	if(opt == 0){
125	ver++;
126	ve.push_back({x, y});
127	}
128	else{
129	if(id[x] > id[y]) swap(x , y);
130	qry.push_back({x, y, ver, (int)qry.size()});
131	}
132	}
133	sort(qry.begin(), qry.end());
134	x = 1, y = 1; int t = 0;
135	for(int i = 0; i < qry.size(); i++){
136	if(x != qry[i].x) move(x, qry[i].x), x = qry[i].x;
137	if(y != qry[i].y) move(y, qry[i].y), y = qry[i].y;
138	int llca = lca(x, y);
139	update(llca);
140	while(t < qry[i].t) make(++t);
141	while(t > qry[i].t) make(t--);
142	ans[qry[i].id] = res;
143	update(llca);
144	}
145	for(int i = 0; i < qry.size(); i++) printf("%lld\n", ans[i]);
146	return 0;
147
148	}