代码:
```cpp
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=133335,V=1e6+3,B=2612;
int n,m,p,q,w[N],b[V],ans[N],res;
struct node{
int l,r,t,id;
bool operator <(const node &y)const{
return l/B!=y.l/B?l<y.l:l/B&1
^(r/B!=y.r/B?r<y.r:r/B&1^t<y.t);
}
}a[N];
struct chg{
int x,k;
}c[N];
void add(int &x){if(!b[x]++) ++res;}
void del(int &x){if(!--b[x]) --res;}
void modify(int &x,int t){
if(c[t].x>=a[x].l&&c[t].x<=a[x].r)
del(w[c[t].x]),add(c[t].k);
swap(w[c[t].x],c[t].k);
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i)
scanf("%d",w+i);
char op;
for(int x,y;m--;){
scanf(" %c%d%d",&op,&x,&y);
if(op=='Q') ++q,a[q]=(node){x,y,p,q};
else c[++p]=(chg){x,y};
}
sort(a+1,a+q+1);
for(int i=1,l=1,r=0,t=0;i<=q;++i){
while(l>a[i].l) add(w[--l]);
while(r<a[i].r) add(w[++r]);
while(l<a[i].l) del(w[l++]);
while(r>a[i].r) del(w[r--]);
while(t<a[i].t) modify(i,++t);
while(t>a[i].t) modify(i,t--);
ans[a[i].id]=res;
}
for(int i=1;i<=q;++i)
printf("%d\n",ans[i]);
return 0;
}
```
~~验证码 hbhh 祭~~
by StarLbright40 @ 2022-06-02 18:58:55
@[星光0000](/user/128570) 排序有问题,改了这个就能过 awa
by SCP_Keter @ 2022-06-02 19:15:24
@[星光0000](/user/128570) 我写了个cmp函数
```cpp
bool cmp(node x,node y){
if(x.l/B!=y.l/B){
return x.l<y.l;
}
if(x.r/B!=y.r/B){
return x.r<y.r;
}
return x.t<y.t;
}
```
by SCP_Keter @ 2022-06-02 19:16:17
@[SCP_Keter](/user/648870) 为什么排序方式会影响正确性啊,不应该只影响用时吗/yiw
by StarLbright40 @ 2022-06-02 19:17:43
@[星光0000](/user/128570) 你那个重载我看不懂?好像不能奇偶排序?
by SCP_Keter @ 2022-06-02 19:19:55
@[星光0000](/user/128570) 后两个点好像是不带修的?
by SCP_Keter @ 2022-06-02 19:23:44
@[SCP_Keter](/user/648870) 莫队的排序只会影响速度吧 转换应该不会影响到
所以why wa?
by Xeqwq @ 2022-06-02 19:28:11
@[整活队长xeq](/user/229373) 但我确实只改了排序就过了? 我也不知道
by SCP_Keter @ 2022-06-02 19:29:36
@[星光0000](/user/128570) `cmp` 函数没有传递性时确实容易出锅,不过您那个函数我没看懂,而且之前我的奇偶排序写假时是 RE。
by Missa @ 2022-06-02 19:30:16
奇偶排序写错了吧
这个是我的
```cpp
bool operator<(Node n1,Node n2)
{
if(k[n1.l]!=k[n2.l]) return k[n1.l]<k[n2.l];
if(k[n1.r]!=k[n2.r]) return (k[n1.l]&1)?k[n1.r]<k[n2.r]:k[n1.r]>k[n2.r];
return n1.stt<n2.stt;
}//那个k数组是当前点所在的块
```
by Xeqwq @ 2022-06-02 19:33:06