链接:lg1903
题解
- 带修改莫队,记录一下当前询问的上一个版本（看起来好像跟可持续化没什么区别）
- 其他的跟普通莫队没什么区别，具体看代码。
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
using namespace std;
const int N=5e4+7;
const int M=1e6+7;
template <typename T>inline void read(T &x){
char c;int sign=1;x=0;
do{c=getchar();if(c=='-')sign=-1;}while(c<'0'||c>'9');
do{x=x*10+c-'0';c=getchar();}while(c>='0'&&c<='9');
x*=sign;
}
struct node{
int l,r,pre,id;
}q[N];
struct node1{
int val,id;
}change[N];
int A[N],pos[N],a[N],col[M],n,m,cntc,cntq;
char s[2];
inline int cmp_pos(node x,node y){
if(pos[x.l]!=pos[y.l])return x.l<y.l;
if(pos[x.r]!=pos[y.r])return x.r<y.r;
return x.pre<y.pre;
}
inline void init(){
read(n);read(m);
int len=sqrt(n);
rep(i,1,n)read(a[i]),pos[i]=(i-1)/len+1;
rep(i,1,m){
scanf("%s",s);
if(s[0]=='Q'){
read(q[++cntq].l);
read(q[cntq].r);
q[cntq].pre=cntc;
q[cntq].id=cntq;
}
else {
read(change[++cntc].id);
read(change[cntc].val);
}
}
sort(q+1,q+cntq+1,cmp_pos);
}
inline void del(ll &ans,int id){
if(--col[id]==0)ans--;
}
inline void add(ll &ans,int id){
if(++col[id]==1)ans++;
}
inline void work(ll &ans,int id,int now){
if(change[id].id>=q[now].l&&change[id].id<=q[now].r){
if(--col[a[change[id].id]]==0)ans--;
if(++col[change[id].val]==1)ans++;
}
swap(change[id].val,a[change[id].id]);
}
void solve(){
init();
ll ans=0;
int l=1,r=0,now=0;;
rep(i,1,cntq){
while(l>q[i].l)add(ans,a[--l]);
while(l<q[i].l)del(ans,a[l++]);
while(r<q[i].r)add(ans,a[++r]);
while(r>q[i].r)del(ans,a[r--]);
while(now<q[i].pre)work(ans,++now,i);
while(now>q[i].pre)work(ans,now--,i);
A[q[i].id]=ans;
}
rep(i,1,cntq)printf("%d\n",A[i]);
}
int main(){
solve();
return 0;
}