BZOJ_2120_数颜色_Set+树状数组+主席树

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。

记录一下第i位置左边第一个和i位置颜色相等的位置L[i]。

然后查询区间[x,y]就相当于查询区间中有多少L[]小于x。

可以用主席树来维护。

修改的话修改原颜色的后继和新颜色的后继和它本身即可，这个可以对所有颜色开一个set来实现。

代码：

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <set>

using namespace std;

#define ms multiset<int>

#define N 10050

ms S[1000050];

int L[N],a[N],n,m,now[1000050];

int t[N*800],ls[N*800],rs[N*800],cnt,root[N];

int lx,ly,ax[N],ay[N];

char opt[10];

void update(int l,int r,int x,int v,int &p) {

    if(!p) p=++cnt;

    t[p]+=v;

    if(l==r) return ;

    int mid=(l+r)>>1;

    if(x<=mid) update(l,mid,x,v,ls[p]);

    else update(mid+1,r,x,v,rs[p]);

}

int query(int l,int r,int x) {

    int i;

    if(l==r) {

        int re=0;

        for(i=1;i<=lx;i++) re+=t[ax[i]];

        for(i=1;i<=ly;i++) re-=t[ay[i]];

        return re;

    }

    int mid=(l+r)>>1;

    int sizls=0;

    for(i=1;i<=lx;i++) sizls+=t[ls[ax[i]]];

    for(i=1;i<=ly;i++) sizls-=t[ls[ay[i]]];

    if(x<=mid) {

        for(i=1;i<=lx;i++) ax[i]=ls[ax[i]];

        for(i=1;i<=ly;i++) ay[i]=ls[ay[i]];

        return query(l,mid,x);

    }else {

        for(i=1;i<=lx;i++) ax[i]=rs[ax[i]];

        for(i=1;i<=ly;i++) ay[i]=rs[ay[i]];

        return query(mid+1,r,x)+sizls;

    }

}

void fix(int p,int v) {

    int i;

    for(i=p;i<=n;i+=i&(-i)) update(0,n,L[p],-1,root[i]);

    L[p]=v;

    for(i=p;i<=n;i+=i&(-i)) update(0,n,L[p],1,root[i]);

}

int main() {

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

    int i,j,x,y;

    for(i=1;i<=n;i++) {

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

        S[a[i]].insert(i);

        L[i]=now[a[i]];

        now[a[i]]=i;

        for(j=i;j<=n;j+=j&(-j)) {

            update(0,n,L[i],1,root[j]);

        }

    }

    while(m--) {

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

        if(opt[0]=='Q') {

            lx=ly=0;

            for(i=y;i;i-=i&(-i)) ax[++lx]=root[i];

            for(i=x-1;i;i-=i&(-i)) ay[++ly]=root[i];

            printf("%d\n",query(0,n,x-1));

        }else {

            int pre=0,nxt=0;

            ms::iterator it;

            it=S[a[x]].lower_bound(x);

            if(it!=S[a[x]].begin()) pre=*(--it),++it;

            it++;

            if(it!=S[a[x]].end()) nxt=*it;

            if(nxt) fix(nxt,pre);

            S[a[x]].erase(x);

            S[y].insert(x);

            a[x]=y;

            int newpre=0,newnxt=0;

            it=S[y].lower_bound(x);

            if(it!=S[y].begin()) newpre=*(--it),++it;

            it++;

            if(it!=S[y].end()) newnxt=*it;

            fix(x,newpre);

            if(newnxt) fix(newnxt,x);

            // printf("%d %d %d %d\n",pre,nxt,newpre,newnxt);

        }

    }

}

巴特西