数颜色
枫林晚
2018-05-12 20:58:16
```cpp
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<iostream>
#include<cstring>
#define num ch-'0'
using namespace std;
const int N=10000+10;
void read(int &x)
{
x=0;char ch;
while(!isdigit(ch=getchar()));
for(x=num;isdigit(ch=getchar());x=x*10+num);
}
int sum;
int n,m;
int a[N],b[N];
int cnt[1000000+10];
int id[N],len;
int ans[N];
int tim[N][3];
struct node{
int l,r,t;
int hao;
bool friend operator <(node a,node b)
{
if(id[a.l]==id[b.l])
{
if(id[a.r]==id[b.r])
{
if(id[a.r]&1) return a.t<b.t;
return a.t>b.t;
}
return a.r<b.r;
}
return a.l<b.l;
}
}q[N];
inline void add(int x)
{
cnt[a[x]]++;
sum+=(cnt[a[x]]==1);
}
inline void del(int x)
{
cnt[a[x]]--;
sum-=(cnt[a[x]]==0);
}
inline void add2(int ti,int l,int r,int k)//1->2 jia k
{
if(l<=tim[ti][0]&&tim[ti][0]<=r)
{
cnt[tim[ti][k]]++;
sum+=(cnt[tim[ti][k]]==1);
}
a[tim[ti][0]]=tim[ti][k];
}
inline void del2(int ti,int l,int r,int k)//2->1 shan k
{
if(l<=tim[ti][0]&&tim[ti][0]<=r)
{
cnt[tim[ti][k]]--;
sum-=(cnt[tim[ti][k]]==0);
}
a[tim[ti][0]]=-1;
}
char que;
int has;
int tot;
int main()
{
read(n);read(m);
len=pow(n,0.666666);
for(int i=1;i<=n;i++) read(a[i]),b[i]=a[i],id[i]=(i-1)/len+1;
int x,y;
has=0;
for(int i=1;i<=m;i++)
{
//scanf("%c",&que);
scanf("%c",&que);
//cout<<que<<endl;
if(que=='Q')
{
tot++;
read(x);read(y);
//cout<<" x y "<<x<<" "<<y<<endl;
q[tot].l=x,q[tot].r=y;
q[tot].t=has;
q[tot].hao=tot;
}
else{
has++;
read(x);read(y);
tim[has][0]=x;tim[has][2]=y;
tim[has][1]=b[x];
b[x]=y;//x shang b[x] -> y
}
//if(que=='Q') cout<<" question "<<tot<<" : "<<q[tot].l<<" to "<<q[tot].r<<" | "<<q[tot].t<<" "<<q[tot].hao<<endl;
}
//cout<<" all questions "<<tot<<endl;
sort(q+1,q+tot+1);
int L,R,T=0;
//for(int i=1;i<=n;i++)
// cout<<" "<<a[i];
//cout<<endl;
for(int i=1;i<=tot;i++)
{
//cout<<" question "<<i<<" : "<<q[i].l<<" to "<<q[i].r<<" | "<<q[i].t<<" "<<q[i].hao<<endl;
if(i==1)
{
L=q[i].l,R=q[i].r;
for(int j=q[i].l;j<=q[i].r;j++)
{
cnt[a[j]]++;
sum+=(cnt[a[j]]==1);
}
//cout<<" sum1 "<<sum<<endl;
while(T<q[i].t) ++T,del2(T,L,R,1),add2(T,L,R,2);
//cout<<" sum2 "<<sum<<endl;
ans[q[i].hao]=sum;
}
else{
while(T<q[i].t) ++T,del2(T,L,R,1),add2(T,L,R,2);
while(T>q[i].t) del2(T,L,R,2),add2(T,L,R,1),T--;
while(L<q[i].l) del(L++);
while(L>q[i].l) add(--L);
while(R<q[i].r) add(++R);
while(R>q[i].r) del(R--);
ans[q[i].hao]=sum;
}
}
for(int i=1;i<=tot;i++)
printf("%d\n",ans[i]);
return 0;
}
```