记录编号	415310	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[国家集训队2011]数颜色	最终得分	100
用户昵称	Hzoi_Hugh	是否通过	通过
代码语言	C++	运行时间	0.373 s
提交时间	2017-06-16 14:26:23	内存使用	4.51 MiB

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<iostream>
#define MAXN 10010
using namespace std;
struct Time
{
   int pos,from,to;
}tim[MAXN];
struct Query
{
   int l,r,tim,id,ans;
}q[MAXN];
int pos[MAXN];
int comp(const Query a,const Query b)
{
   return pos[a.l]<pos[b.l]||(pos[a.l]==pos[b.l]&&a.r<b.r);
}
int cmp(const Query a,const Query b)
{
    return a.id<b.id;
}
int len,t,n,l,r,ans,m,qm,tmo=1,a[MAXN],tmp[1000010];
inline void read()
{
   scanf("%d%d",&n,&m);
   len=(int)(sqrt(n+0.5));
   for(int i=1;i<=n;i++)
   {
      scanf("%d",&a[i]);
      pos[i]=(i-1)/len+1;
   }
   for(int i=1;i<=m;i++)
   {
      char s[2];
      scanf("%s",s);
      if(s[0]=='Q')
      {
        qm++;
        scanf("%d%d",&q[qm].l,&q[qm].r);
        q[qm].tim=tmo;
        q[qm].id=qm;
      }
      else
      {
        scanf("%d%d",&tim[tmo].pos,&tim[tmo].to);
        tim[tmo].from=a[tim[tmo].pos];
        a[tim[tmo].pos]=tim[tmo].to;
        tmo++;
      }
   }
   sort(q+1,q+qm+1,comp);
   l=r=ans=1;
   tmp[a[1]]=1;
   t=tmo;
}
inline void viato(int p)
{
   a[tim[p].pos]=tim[p].to;
   if(l<=tim[p].pos&&tim[p].pos<=r)
   {
       tmp[tim[p].from]--;
       if(tmp[tim[p].from]==0)ans--;
       tmp[tim[p].to]++;
       if(tmp[tim[p].to]==1)ans++;
   }
}
inline void viafrom(int p)
{
   a[tim[p].pos]=tim[p].from;
   if(l<=tim[p].pos&&tim[p].pos<=r)
   {
       tmp[tim[p].to]--;
       if(tmp[tim[p].to]==0)ans--;
       tmp[tim[p].from]++;
       if(tmp[tim[p].from]==1)ans++;
   }
}
inline void do_(int p,int d)
{
   tmp[a[p]]+=d;
   if(d==-1&&tmp[a[p]]==0)ans--;
   if(d==1&&tmp[a[p]]==1)ans++;
}
inline void work()
{
   for(int i=1;i<=qm;i++)
   {
      while(t<q[i].tim)viato(t++);
      while(t>q[i].tim)viafrom(--t);
      while(l<q[i].l)do_(l++,-1);
      while(l>q[i].l)do_(--l,1);
      while(r<q[i].r)do_(++r,1);
      while(r>q[i].r)do_(r--,-1);
      q[i].ans=ans;
   }
   sort(q+1,q+qm+1,cmp);
   for(int i=1;i<=qm;i++)
    printf("%d\n",q[i].ans);
}
int main()
{
    freopen("nt2011_color.in","r",stdin);
	freopen("nt2011_color.out","w",stdout);
    read();
    work();
    return 0;
}