然后顺带求调。
```cpp
#include <stdio.h>
#include <cmath>
#include <algorithm>
using namespace std;
const int N=133335;
int block,res,n,m,i;
int l=1,r=0,t=0,cnt,len,x,y;
int ret[N];
class update
{
public:
int pos,nxt,pre;
}chg[N];
class query
{
public:
int l,r,tim,id;
int lpos,rpos;
query()
{
}
query(int ll,int rr,int timm,int idd):l(ll),r(rr),tim(timm),id(idd),lpos(ll/block),rpos(rr/block)
{
}
inline const bool operator<(const query &other)const
{
if(lpos!=other.lpos)
return lpos<other.lpos;
else if(rpos!=other.rpos)
return rpos<other.rpos;
else
return tim<other.tim;
}
}mid,q[N];
int v[N];
int p[N];
inline void add(int x)
{
res+=!(p[v[x]]++);
return ;
}
inline void del(int x)
{
res-=!(--p[v[x]]);
return ;
}
inline void tsolve(int x,int l,int r)
{
if(l<=chg[x].pos&&chg[x].pos<=r)
{
if(--p[v[chg[x].pos]]==0)
--res;
if(++p[chg[x].nxt]==1)
++res;
}
swap(chg[x].pre,v[chg[x].pos]);
return ;
}
int main()
{
char opt;
scanf("%d %d",&n,&m);
block=pow(n,1./3);
for(i=1;i<=n;++i)
scanf("%d",v+i);
for(i=1;i<=m;++i)
{
scanf(" %c %d %d",&opt,&x,&y);
if(opt=='R')
{
++cnt;
chg[cnt].pos=x;
chg[cnt].nxt=y;
chg[cnt].pre=v[x];
v[chg[cnt].pos]=chg[cnt].nxt;
}else
{
// printf("%d %d %d %d\n",x,y,cnt,len);
mid=query(x,y,cnt,len+1);
q[++len]=mid;
}
}
// for(i=1;i<=len;++i)
// {
// printf("%d %d %d\n",q[i].l,q[i].r,q[i].tim);
// }
for(i=cnt;i>=1;--i)
{
// printf("%d %d %d\n",chg[i].pos,chg[i].pre,chg[i].nxt);
v[chg[i].pos]=chg[i].pre;
}
sort(q+1,q+len+1);
for(i=1;i<=len;++i)
{
while(q[i].r>r)
add(++r);
while(q[i].l<l)
add(--l);
while(q[i].r<r)
del(r--);
while(q[i].l>l)
del(l++);
while(q[i].tim>t)
tsolve(++t,q[i].l,q[i].r);
while(q[i].tim<t)
tsolve(t--,q[i].l,q[i].r);
ret[q[i].id]=res;
// printf("%d : %d %d %d %d %d %d %d\n",i,q[i].id,t,l,r,q[i].l,q[i].r,res);
}
for(i=1;i<=len;++i)
printf("%d\n",ret[i]);
}
```
目前没分
by Etinorally @ 2023-01-09 18:23:25
五角星好强，拜谢五角星
by Mikefeng @ 2023-01-09 18:33:12
变态啊，为什么把数组再开大十倍就过了
by Etinorally @ 2023-01-09 18:35:57
@[bye_wjx](/user/575994) 因为颜色的值域是1e6
by Mikefeng @ 2023-01-09 18:48:59
@[Mikefeng](/user/406832) 好的，thx
by Etinorally @ 2023-01-09 19:01:00