[UVa12345] Dynamic len (带 修 )

题意：有n个数编号从0→n-1,两种操作： 
           Q L R:询问编号为L→R-1的数中共有多少种不同的数  
           M X Y：将编号为X的数改为Y 
           共有m个操作

题目 链接 :  https://vjudge.net/problem/UVA-12345

#include<bits/stdc++.h>

#define LL long long

#define ULL unsigned long long

#define rep(i,j,k) for(int i=j;i<=k;i++)

#define dep(i,j,k) for(int i=k;i>=j;i--)

#define INF 0x3f3f3f3f

#define mem(i,j) memset(i,0,sizeof(i))

#define make(i,j) make_pair(i,j)

using namespace std;

const int N=1e6+;

int a[N],pos[N],num[N],now[N],ans[N],l=,r=,tmp;

struct noq {

    int l,r,id,t;

}q[N];

struct noc {

    int x,old,ne;

}c[N];

bool cmp(noq a,noq b) {

    if(pos[a.l]==pos[b.l]) {

        if(pos[a.r]==pos[b.r]) return a.t<b.t;

        return pos[a.r]<pos[b.r];

    }

    return pos[a.l]<pos[b.l];

}

void add(int x,int d) {

    num[x]+=d;

    if(d> && num[x]==) tmp++;

    else if(d< && num[x]==) tmp--;

}

void go(int x,int ne) {

    if(l<=x && x<=r) {

        add(a[x],-); add(ne,);

    }

    a[x]=ne;

}

int main() {

    int n,m; int head=,tail=;

    scanf("%d %d",&n,&m); int M=(int)pow(n,0.666666);

    rep(i,,n) {

        scanf("%d",&a[i]);

        now[i]=a[i];

        pos[i]=(i-)/M;

    }

    rep(i,,m) {

        char ch[]; int x,y;

        scanf("%s",ch);

        scanf("%d %d",&x,&y); x++;

        if(ch[]=='Q') q[++head]=(noq){x,y,head,tail};

        else {

            c[++tail]=(noc){x,now[x],y};

            now[x]=y;

        }

    }

    sort(q+,q++head,cmp); int t=;

    rep(i,,head) {

        while(t<q[i].t) go(c[t+].x,c[t+].ne),++t;

        while(t>q[i].t) go(c[t].x,c[t].old),--t;

        while(l<q[i].l) add(a[l++],-);

        while(l>q[i].l) add(a[--l],);

        while(r<q[i].r) add(a[++r],);

        while(r>q[i].r) add(a[r--],-);

        ans[q[i].id]=tmp;

    }

    rep(i,,head) printf("%d\n",ans[i]);

    return ;

}