这排序都不对吧。
by E_firework @ 2022-07-29 22:11:18
28行有问题,撤销一次操作不等同于还原为初始状态
by E_firework @ 2022-07-29 22:15:03
数组也开小l
by E_firework @ 2022-07-29 22:22:04
@[xbb2](/user/174806)
```cpp
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
int c[1000005],a[N],ans[N],b[N],sum=0,n,m,maxx,cnt1=0,cnt2=0;//注释表示原本代码中可能有误的地方
struct tip_q{int l,r,id,t;}q[N];
struct tip_r{int p,col;}p[N];
inline bool cmp(tip_q a,tip_q b){//
if(a.l/maxx!=b.l/maxx)return a.l<b.l;
else if(a.r/maxx!=b.r/maxx) return a.r<b.r;
else return a.t<b.t;
}
void add(int x){if(c[x]==0){++sum;}++c[x];}
void del(int x){--c[x];if(c[x]==0){--sum;}}
int main(){
cin>>n>>m,maxx=pow(n,(double)2/(double)3);
for(int i=1;i<=n;i++)scanf("%d",&a[i]),b[i]=a[i];
for(int i=1;i<=m;i++){
char c;cin>>c;
if(c=='Q')cnt1++,scanf("%d%d",&q[cnt1].l,&q[cnt1].r),q[cnt1].id=cnt1,q[cnt1].t=cnt2;//
else cnt2++,scanf("%d%d",&p[cnt2].p,&p[cnt2].col);//
}
sort(q+1,q+1+cnt1,cmp);
for(int i=1,l=1,r=0,t=0;i<=cnt1;++i){
while(l>q[i].l)add(a[--l]);
while(r<q[i].r)add(a[++r]);
while(l<q[i].l)del(a[l++]);
while(r>q[i].r)del(a[r--]);
for(;t>q[i].t;){
if(l<=p[t].p&&p[t].p<=r)del(a[p[t].p]),swap(a[p[t].p], p[t].col),add(a[p[t].p]);//
else swap(a[p[t].p], p[t].col);--t;
}
for(;t<q[i].t;){
++t;if(l<=p[t].p&&p[t].p<=r)del(a[p[t].p]),swap(a[p[t].p], p[t].col),add(a[p[t].p]);//
else swap(a[p[t].p], p[t].col);
}
ans[q[i].id]=sum;
}
for(int i=1;i<=cnt1;i++)printf("%d\n",ans[i]);
return 0;
}
by E_firework @ 2022-07-29 22:23:36
@[E_firework](/user/488539) Thanks♪(・ω・)ノ
by xbb2 @ 2022-07-29 22:25:11
但问一下,为什么 ``` &p[++cnt2].p ``` 不可以
by xbb2 @ 2022-07-29 22:26:36
逗号的运算顺序,改成 `scanf("%d%d",&q[cnt1].l,&q[++cnt1].r)`
by E_firework @ 2022-07-30 07:28:19