【BZOJ 2120】数颜色【分块/莫队】

题意

给出n个数字和m个操作。操作有两种。1：查询区间[l,r]内不同种类得数字个数。2: 将下标为p得数字修改为v

分析

如果不是修改操作的话，用莫队贼简单就可以水过，但是因为带了修改就有一些麻烦了。

分块

　开一个数组pre[i]记录上一个和第i个元素相同元素得位置。那么对于区间[l,r]，当pre[i]<l的时候，ans++。完整块内就可以直接二分查找，不完整块直接暴力。修改是直接暴力修改因为它保证修改操作不会超过1000次。

下面是代码

 #include <cstdio>

 #include <cstring>

 #include <algorithm>

 #include <iostream>

 #include <cmath>

 using namespace std;

 const int maxn=+;

 int a[maxn],belong[maxn],L[maxn],R[maxn],pre[maxn];

 int last[+],b[maxn];

 int n,m,cnt,block;

 void update(int p,int v){

     for(int i=;i<=n;i++)

         last[a[i]]=;

     a[p]=v;

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

         b[i]=last[a[i]];

         last[a[i]]=i;

     }

     for(int i=;i<=cnt;i++){

         for(int j=L[i];j<=R[i];j++)

             pre[j]=b[j];

         sort(pre+L[i],pre+R[i]+);

     }

 }

 int Find(int p,int v){

     int res=;

     int l=L[p],r=R[p];

     while(l<=r){

         int m=l+(r-l)/;

         if(pre[m]<v){

             res=m;

             l=m+;

         }else{

             r=m-;

         }

     }

     return res-L[p]+;

 }

 int query(int l,int r){

     int res=;

     if(belong[l]==belong[r]){

         for(int i=l;i<=r;i++){

             if(b[i]<l)

                 res++;

         }

         return res;

     }

     for(int i=l;i<=R[belong[l]];i++)

         if(b[i]<l)

             res++;

     for(int i=L[belong[r]];i<=r;i++)

         if(b[i]<l)

             res++;

     for(int i=belong[l]+;i<belong[r];i++){

         res+=Find(i,l);

     }

     return res;

 }

 int main(){

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

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

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

         b[i]=last[a[i]];

         last[a[i]]=i;

     }

     block=sqrt(n);cnt=n/block;

     if(n%block)cnt++;

     for(int i=;i<=n;i++)

         belong[i]=(i-)/block+;

     for(int i=;i<=cnt;i++)

         L[i]=(i-)*block+,R[i]=i*block;

     R[cnt]=n;

     for(int i=;i<=cnt;i++){

         for(int j=L[i];j<=R[i];j++)

             pre[j]=b[j];

         sort(pre+L[i],pre+R[i]+);

     }

     char c;

     int l,r;

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

         scanf(" %c",&c);

         if(c=='Q'){

             scanf("%d%d",&l,&r);

             printf("%d\n",query(l,r));

         }else{

             scanf("%d%d",&l,&r);

             update(l,r);

         }

     }

 return ;

 }

莫队

对于莫队来说，难点就在于它带有修改操作。我们怎么来处理修改呢？我们在除了l，r指针以外再增加一个指针now，用类似l和r得方式进行维护。

 #include <cstdio>

 #include <cstring>

 #include <algorithm>

 #include <iostream>

 #include <cmath>

 using namespace std;

 const int maxn=+;

 int belong[maxn],val[maxn];

 struct Node{

     int L,R,id,tim;

     bool operator<(const Node& rhs)const{

         return belong[L]==belong[rhs.L]?(belong[R]==belong[rhs.R]?tim<rhs.tim:R<rhs.R):L<rhs.L;

     }

     int ans;

 }ask[maxn];

 struct Up{

     int p,v,z;

 }up[maxn];

 int num1,num2;

 int cmp(Node a,Node b){

     return a.id<b.id;

 }

 int n,q;

 int f[+],ans,block,l,r,now;

 void update(int p,int addv){

     if(addv>){

         f[val[p]]++;

         if(f[val[p]]==)

             ans++;

     }else{

         f[val[p]]--;

         if(f[val[p]]==)

             ans--;

     }

 }

 void in_time(int x){

     if(up[x].p>=l&&up[x].p<=r){

         update(up[x].p,-);

     }

     up[x].z=val[up[x].p];

     val[up[x].p]=up[x].v;

     if(up[x].p>=l&&up[x].p<=r){

         update(up[x].p,);

     }

 }

 void out_time(int x){

     if(up[x].p>=l&&up[x].p<=r)

         update(up[x].p,-);

     val[up[x].p]=up[x].z;

     if(up[x].p>=l&&up[x].p<=r)

         update(up[x].p,);

 }

 void solve(){

     l=,r=,now=;

     for(int i=;i<=num1;i++){

         if(r<ask[i].R){

             for(r=r+;r<ask[i].R;r++)

                 update(r,);

             update(r,);

         }

         if(l>ask[i].L){

             for(l=l-;l>ask[i].L;l--)

                 update(l,);

             update(l,);

         }

         if(r>ask[i].R){

             for(;r>ask[i].R;r--)

                 update(r,-);

         }

         if(l<ask[i].L){

             for(;l<ask[i].L;l++)

                 update(l,-);

         }

         if(now<ask[i].tim){

             for(now=now+;now<ask[i].tim;now++)

                 in_time(now);

             in_time(now);

         }

         if(now>ask[i].tim){

             for(;now>ask[i].tim;now--)

                 out_time(now);

         }

         ask[i].ans=ans;

     }

 }

 int main(){

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

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

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

     }

     block=sqrt(n);

     for(int i=;i<=n;i++)

         belong[i]=(i-)/block+;

     char c;

     int l,r;

     for(int i=;i<=q;i++){

         scanf(" %c",&c);

         if(c=='Q'){

             num1++;

             scanf("%d%d",&ask[num1].L,&ask[num1].R);

             ask[num1].id=num1;ask[num1].tim=num2;

         }else{

             num2++;

             scanf("%d%d",&up[num2].p,&up[num2].v);

             up[num2].z=;

         }

     }

     sort(ask+,ask++num1);

     solve();

     sort(ask+,ask++num1,cmp);

     for(int i=;i<=num1;i++)

         printf("%d\n",ask[i].ans);

 return ;

 }

巴特西

【BZOJ 2120】数颜色【分块/莫队】

最新文章

热门文章