@[yzq_yzq](/user/560006)
by qwq___qaq @ 2022-10-09 23:31:42
@[_sto_pengzijun_orz_](/user/556362) 时间轴莫队吗？
by yzq_yzq @ 2022-10-10 13:54:43
我测了一下，把你的时间轴删了也是40分，说明肯定是时间轴写错了
by yzq_yzq @ 2022-10-10 14:26:46
c，我一个小时没改完
by yzq_yzq @ 2022-10-10 14:30:20
@[yzq_yzq](/user/560006) 我两晚上没改出来
by qwq___qaq @ 2022-10-10 22:42:33
@[_sto_pengzijun_orz_](/user/556362)
```cpp
#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5,maxt=1e6+5;
int cnt[maxt],l=1,r,c,n,m,s,len,num,tot,ans[maxn],a[maxn],b[maxn],t[maxn],pre[maxn],nxt[maxn],now[maxn];
struct node{
int l,r,c,id;
inline bool operator <(const node &o) const{
return t[l]<t[o.l]||(t[l]==t[o.l]&&t[r]<t[o.r])||(t[l]==t[o.l]&&t[r]==t[o.r]&&c<o.c);
}
}f[maxn];
inline int read(){
int res=0,f=0;
char ch=getchar();
while(ch<'0'||ch>'9'){
f|=(ch=='-');
ch=getchar();
}
while(ch>='0'&&ch<='9'){
res=(res<<1)+(res<<3)+(ch^'0');
ch=getchar();
}
return f?-res:res;
}
inline void add(int t){
++cnt[a[t]];
if(cnt[a[t]]==1)
++s;
}
inline void del(int t){
if(cnt[a[t]]==1)
--s;
--cnt[a[t]];
}
inline void rgt(int t){//仔细想一想cnt的含义是什么
if(l<=now[t]&&now[t]<=r) del(now[t]);
a[now[t]]=nxt[t];
if(l<=now[t]&&now[t]<=r) add(now[t]);
}
inline void lft(int t){
if(l<=now[t]&&now[t]<=r) del(now[t]);
a[now[t]]=pre[t];
if(l<=now[t]&&now[t]<=r) add(now[t]);
}
int main(){
n=read(),m=read();
for(int i=1;i<=n;++i) a[i]=b[i]=read();
len=pow(n,2.0/3.0);
for(int i=1;i<=(n+len-1)/len;++i)
for(int j=(i-1)*len+1;j<=min(n,i*len);++j)
t[j]=i;
for(int i=1;i<=m;++i){
char ch=getchar();
while(ch!='Q'&&ch!='R')
ch=getchar();
if(ch=='Q'){
++num;
f[num].l=read(),f[num].r=read(),f[num].c=tot,f[num].id=num;
} else{
++tot;
now[tot]=read();
pre[tot]=b[now[tot]];
b[now[tot]]=nxt[tot]=read();
}
}
sort(f+1,f+num+1);
for(int i=1;i<=num;++i){
while(l>f[i].l) add(--l);
while(r<f[i].r) add(++r);
while(l<f[i].l) del(l++);
while(r>f[i].r) del(r--);
while(c<f[i].c) rgt(++c);
while(c>f[i].c) lft(c--);
ans[f[i].id]=s;
}
for(int i=1;i<=num;++i)
printf("%d\n",ans[i]);
return 0;
}
by E_firework @ 2022-10-12 15:00:38