BZOJ2120 数颜色

---

Description

墨墨购买了一套N支彩色画笔（其中有些颜色可能相同），摆成一排，你需要回答墨墨的提问。墨墨会像你发布如下指令：

1、 Q L R代表询问你从第L支画笔到第R支画笔*有几种不同颜色的画笔。

2、 R P Col 把第P支画笔替换为颜色Col。

为了满足墨墨的要求，你知道你需要干什么了吗？

Input

第1行两个整数N，M，分别代表初始画笔的数量以及墨墨会做的事情的个数。第2行N个整数，分别代表初始画笔排中第i支画笔的颜色。第3行到第2+M行，每行分别代表墨墨会做的一件事情，格式见题*分。

Output

对于每一个Query的询问，你需要在对应的行中给出一个数字，代表第L支画笔到第R支画笔*有几种不同颜色的画笔。

Sample Input

6 5

1 2 3 4 5 5

Q 1 4

Q 2 6

R 1 2

Q 1 4

Q 2 6

Sample Output

4

4

3

4

HINT

对于100%的数据，N≤10000，M≤10000，修改操作不多于1000次，所有的输入数据中出现的所有整数均大于等于1且不超过10^6。

---

挺好的一道带修改莫队入门题

一开始没有考虑在修改的基础上进行累加，不能一直从原状态上进行累加，因为时间是固定的，所以我们可以保证修改一定是有序的

就是代码中的last数组

其他没什么好说的，但是提醒一下，虽然sqrt（n）也可以过，但是siz取n的三分之二次方最优

---

#include<bits/stdc++.h>

using namespace std;

#define N 1000010

struct Node{int pos,x,y;}t[N];

struct Ask{int l,r,id,tim;}p[N];

int block[N],a[N],last[N],ans[N],cnt[N];

int n,m,totp=0,tott=0;

int l=1,r=0,tmp=0,ansnow=0;

bool cmp1(Ask a,Ask b){

    if(block[a.l]==block[b.l])return a.r<b.r;

    else return block[a.l]<block[b.l];

}

void modify(int pos,int y){

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

        if(--cnt[a[pos]]==0)ansnow--;

        a[pos]=y;

        if(++cnt[a[pos]]==1)ansnow++;

    }else a[pos]=y;

}

void update(int pos,int typ){

    if(typ==1)ansnow+=(++cnt[a[pos]]==1);

    else ansnow-=(--cnt[a[pos]]==0);

}

int main(){

    scanf("%d%d",&n,&m);

    for(int i=1;i<=n;i++)scanf("%d",&a[i]),last[i]=a[i];

    for(int i=1;i<=m;i++){

        char c[5];int x,y;

        scanf("%s%d%d",c,&x,&y);

        if(c[0]=='Q')p[++totp]=(Ask){x,y,totp,tott};

        else{

            t[++tott]=(Node){x,last[x],y};

            last[x]=y;

        }

    }

    int siz=sqrt(n);

    for(int i=1;i<=n;i++)block[i]=(i-1)/siz+1;

    sort(p+1,p+totp+1,cmp1);

    for(int i=1;i<=totp;i++){

        while(tmp<p[i].tim)++tmp,modify(t[tmp].pos,t[tmp].y);

        while(tmp>p[i].tim)modify(t[tmp].pos,t[tmp].x),tmp--;

        while(l<p[i].l)update(l++,-1);

        while(l>p[i].l)update(--l,1);

        while(r<p[i].r)update(++r,1);

        while(r>p[i].r)update(r--,-1);

        ans[p[i].id]=ansnow;

    }

    for(int i=1;i<=totp;i++)printf("%d\n",ans[i]);

    return 0;

}