数颜色

枫林晚 · 2018-05-12 20:58:16 · 个人记录

#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;
}