Lvat_s Blog

很多人都是使用大型数据结构写的。

我是整体二分+树状数组维护，思路是Zig_Zag大神博客上的。

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<set>
#include<algorithm>
using namespace std;
 
const int N=30005,M=1000005;
 
int n,m,col[N],cnt,num,BIT[N],ans[N],tmp[N];
set<int> Color[M];
 
struct Ask{
int l,r,opt,cur,id;
}ask[N],Q1[N],Q2[N];
 
int lowbit(int x){return x&(-x);}
void Add(int pos,int val){while(pos<=n){BIT[pos]+=val;pos+=lowbit(pos);}}
int Sum(int pos){int ans=0;while(pos){ans+=BIT[pos];pos-=lowbit(pos);}return ans;}
int Pre(int x,int c){set<int>::iterator I=Color[c].lower_bound(x);if(I!=Color[c].begin())return *(--I);return 0;}
int Nxt(int x,int c){set<int>::iterator I=Color[c].upper_bound(x);if(I!=Color[c].end())return *I;return 0;}
 
void Div2x(int l,int r,int nl,int nr){
if(nl>nr)return;
int mid=l+r>>1,M1=0,M2=0;
if(l==r){for(int i=nl;i<=nr;i++)if(ask[i].opt==3)ans[ask[i].id]=ask[i].cur;return;}
for(int i=nl;i<=nr;i++){
    if(ask[i].opt==1 && ask[i].r<=mid)Add(ask[i].l,1);
    if(ask[i].opt==2 && ask[i].r<=mid)Add(ask[i].l,-1);
    if(ask[i].opt==3)tmp[i]=Sum(ask[i].r)-Sum(ask[i].l-1);
}
for(int i=nl;i<=nr;i++){
    if(ask[i].opt==1 && ask[i].r<=mid)Add(ask[i].l,-1);
    if(ask[i].opt==2 && ask[i].r<=mid)Add(ask[i].l,1);
}
for(int i=nl;i<=nr;i++){
    if(ask[i].opt==3){
        if(ask[i].l<=mid)Q1[++M1]=ask[i];
        else {ask[i].cur+=tmp[i];Q2[++M2]=ask[i];}
    }
    else {
        if(ask[i].r<=mid)Q1[++M1]=ask[i];
        else Q2[++M2]=ask[i];
    }
}
for(int i=1;i<=M1;i++)ask[nl+i-1]=Q1[i];
for(int i=1;i<=M2;i++)ask[nr-M2+i]=Q2[i];
Div2x(l,mid,nl,nl+M1-1);
Div2x(mid+1,r,nl+M1,nr);
}
 
int main(){
freopen("2120.in","r",stdin);
freopen("2120.out","w",stdout);
scanf("%d %d",&n,&m);
for(int i=1;i<=n;i++){
    scanf("%d",&col[i]);
    Color[col[i]].insert(i);
    ask[++num].opt=1;
    int p=Pre(i,col[i]);
    ask[num].l=i;
    ask[num].r=p;
}
for(int i=1;i<=m;i++){
    char s[5];
    int l,r;
    scanf("%s %d %d",s,&l,&r);
    if(s[0]=='Q'){
        ask[++num].opt=3;
        ask[num].id=++cnt;
        ask[num].l=l;
        ask[num].r=r;
    }
    else {
        int Ll=Pre(l,col[l]),Lr=Pre(l,r),Rl=Nxt(l,col[l]),Rr=Nxt(l,r);
        if(Rl){
            ask[++num].opt=2;ask[num].l=Rl;ask[num].r=l;
            ask[++num].opt=1;ask[num].l=Rl;ask[num].r=Ll;
        }
        ask[++num].opt=2;ask[num].l=l;ask[num].r=Ll;
        ask[++num].opt=1;ask[num].l=l;ask[num].r=Lr;
        if(Rr){
            ask[++num].opt=2;ask[num].l=Rr;ask[num].r=Lr;
            ask[++num].opt=1;ask[num].l=Rr;ask[num].r=l;
        }
        Color[col[l]].erase(l);
        Color[r].insert(l);
        col[l]=r;
    }
}
Div2x(0,M,1,num);
for(int i=1;i<=cnt;i++)printf("%d\n",ans[i]);
return 0;
}