(luogu1903)数颜色

原题链接

思路:

这题是带修莫队的模板题

实际上带修莫队的操作和普通莫队大致相同,区别在于带修莫队多了一个“时间轴”。

首先将修改与查询分开记录。每个查询记录一个值表示查询前有多少次修改(即“时间”)。处理查询时通过“时间”来决定修改或撤销修改。

根据计算,块大小为$\sqrt[3]{nt}$时可达最优的时间复杂度$O(\sqrt[3]{n^4t})$,其中$t$为修改次数,需要注意$t=0$的情况。

代码:

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
#include <cmath>
#include <iostream>
#include <algorithm>
using namespace std;
const int Mn(200500), Ma(1000500);

int bln; //块长
int arr[Mn]; //原数组
inline int calcb(int x) { //计算x所在分块编号
return x/bln + (x%bln==0);
}
struct Qyd {
int l, r, t, id;
bool operator < (const Qyd& rhs) const { //询问排序
if(calcb(l)==calcb(rhs.l)) {
if(calcb(r)==calcb(rhs.r)) {
return t < rhs.t;
}
return r < rhs.r;
}
return l < rhs.l;
}
}aq[Mn]; //所有询问
int ans[Mn]; //询问答案

struct Mfd { //修改
int p, x, prx; //修改位置,修改后的数,修改前的数
}am[Mn]; //所有修改

int cnt[Ma]; //计数数组

int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n,m;
cin >> n >> m;
for(int i(1);i<=n;++i) {
cin >> arr[i];
}
int cq(0),ct(0); //询问数,修改数
for(int i(1);i<=m;++i) {
char o;
int x, y;
cin >> o >> x >> y;
if(o=='Q') {
++cq;
aq[cq] = {x,y,ct,cq};
} else {
am[++ct] = {x,y,arr[x]};
arr[x] = y; //记录修改时同时直接修改数组
}
}
bln = ceil(pow(1ll*n*(ct==0?1:ct),(ct==0?1./2:1./3))); //注意t==0的判断,此时退化为普通莫队
sort(aq+1,aq+cq+1);
int l(1),r(0),t(ct),tans(0); //时间设置为ct可不还原数组
for(int i(1);i<=cq;++i) {
Qyd& q(aq[i]);
while(l>q.l) {
--l;
++cnt[arr[l]];
if(cnt[arr[l]]==1) {
++tans;
}
}
while(r<q.r) {
++r;
++cnt[arr[r]];
if(cnt[arr[r]]==1) {
++tans;
}
}
while(l<q.l) {
--cnt[arr[l]];
if(cnt[arr[l]]==0) {
--tans;
}
++l;
}
while(r>q.r) {
--cnt[arr[r]];
if(cnt[arr[r]]==0) {
--tans;
}
--r;
}
while(t<q.t) { //修改
++t;
Mfd& f(am[t]);
arr[f.p] = f.x;
if(f.p>=l && f.p<=r) { //修改位置在询问区间中需要对计数数组和临时答案进行修改
--cnt[f.prx];
++cnt[f.x];
if(f.prx!=f.x && cnt[f.prx]==0) {
--tans;
}
if(f.prx!=f.x && cnt[f.x]==1) {
++tans;
}
}
}
while(t>q.t) { //撤回
Mfd& f(am[t]);
arr[f.p] = f.prx;
if(f.p>=l && f.p<=r) { //同上
--cnt[f.x];
++cnt[f.prx];
if(f.prx!=f.x && cnt[f.x]==0) {
--tans;
}
if(f.prx!=f.x && cnt[f.prx]==1) {
++tans;
}
}
--t;
}
ans[q.id] = tans;
}
for(int i(1);i<=cq;++i) {
printf("%d\n",ans[i]);
}
return 0;
}