【带修莫队】洛谷P1903 数颜色 维护队列
2021-05-07 20:38:00 # ACM

题链

1、 $Q$ $L$ $R$代表询问你从第$L$支画笔到第$R$支画笔中共有几种不同颜色的画笔。

2、 $R$ $P$ $Col$ 把第$P$支画笔替换为颜色$Col$。

带修改莫队；

学玩普通莫队再看带修改莫队，OI-wiki上讲的通俗易懂；

对比主要是这几点：

1.分块$unit = pow(n,2.0/3.0)$;

2.对询问排序是先排左区间是否在同一个块，再排右区间，然后是时间

3.将询问和修改划分成两个数组，莫队将左右指针移动到询问区间过后再考虑修改问题，已知本次询问的$time$，然后在修改数组上将$time$之前的修改都跑一遍，其中修改值与被修改值是$swap$相互替换，因为可能要回退，也就是换回来。

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
125
126
127
128
129
130
131
#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define ULL unsigned long long
#define Pair pair<LL,LL>
#define ls rt<<1
#define rs rt<<1|1
#define Pi acos(-1.0)
#define eps 1e-6
#define DBINF 1e100
#define mod 1000000007
#define MAXN 1e18
#define MS 1000009

LL n,m;
int a[MS];
struct node{
	int l,r,id;
}ask[MS];
int asknum;
int unit;

struct nod{
	int pos,tar,id;
}alt[MS];
int altnum;

int v[MS];

int ac[MS]; 

bool cmp(node t1,node t2){
	if(t1.l/unit != t2.l/unit) return t1.l < t2.l;
	if(t1.r/unit != t2.r/unit) return t1.r < t2.r;
	return t1.id < t2.id;
}

int main() {
	ios::sync_with_stdio(false);
	cin >> n >> m;
	for(int i=1;i<=n;i++){
		cin >> a[i];
	}
	for(int i=1;i<=m;i++){
		char op;
		cin >> op;
		if(op == 'Q'){
			int l,r;
			cin >> l >> r;
			ask[++asknum] = {l,r,i};
		}
		else if(op == 'R'){
			int pos,tar;
			cin >> pos >> tar;
			alt[++altnum] = {pos,tar,i};
		}
	}
	unit = pow(n,2.0/3.0);
	sort(ask+1,ask+asknum+1,cmp);
	int ans = 0;
	int L = 1 ,R = 0;
	int time = 0;
	for(int i=1;i<=asknum;i++){
		int l = ask[i].l;
		int r = ask[i].r;
		int id = ask[i].id;
		while(L < l){
			v[a[L]]--;
			if(v[a[L]] == 0) ans--;
			L++;
		}
		while(L > l){
			L--;
			v[a[L]]++;
			if(v[a[L]] == 1) ans++;
		}
		while(R < r){
			R++;
			v[a[R]]++;
			if(v[a[R]] == 1) ans++;
		}
		while(R > r){
			v[a[R]]--;
			if(v[a[R]] == 0) ans--;
			R--;
		}
		
		while(alt[time+1].id < id && time+1 <= altnum){
			time++;
			int altpos = alt[time].pos;
			int alttar = alt[time].tar;
			if(L <= altpos && altpos <= R){
				v[a[altpos]]--;
				if(v[a[altpos]] == 0) ans--;
				swap(a[altpos],alt[time].tar);
				v[a[altpos]]++;
				if(v[a[altpos]] == 1) ans++;
			}
			else{
				swap(a[altpos],alt[time].tar);
			}
		}
		while(alt[time].id > id){
			int altpos = alt[time].pos;
			int alttar = alt[time].tar;
			if(L <= altpos && altpos <= R){
				v[a[altpos]]--;
				if(v[a[altpos]] == 0) ans--;
				swap(a[altpos],alt[time].tar);
				v[a[altpos]]++;
				if(v[a[altpos]] == 1) ans++;
			}
			else{
				swap(a[altpos],alt[time].tar);
			}
			time--;
		}
		
		ac[ask[i].id] = ans;
		
	}
	
	for(int i=1;i<=m;i++){
		if(ac[i]){
			cout << ac[i] << "\n";
		}
	}
	

	return 0;
}
Prev
2021-05-07 20:38:00 # ACM
Next