【分块】bzoj2120 数颜色

分块，在每个点记录一下它之前离它最近的相同颜色的位置pre[i]，显然问题转化成了求[l,r]中pre[i]<l的值的个数。

这是分块擅长的，在每个块内记录有序表，查询时对零散的暴力，整块的二分即可。

修改时有点麻烦，设修改a[p]。

可能会对pre[p]产生影响；

可能会对p位置之后的第一个与a[p]修改前相等的值的pre 产生影响；

可能会对p位置之后的第一个与a[p]修改后相等的值的pre 产生影响。

细节蛮多，调了很久。<---蒟蒻。

 #include<cstdio>

 #include<cmath>

 #include<cstring>

 #include<algorithm>

 using namespace std;

 int n,m,sz,sum,l[],r[],num[],pre[],preb[],a[],x,y,pos[];

 int Res,Num;char C,CH[];

 inline int G()

 {

     Res=;C='*';

     while(C<''||C>'')C=getchar();

     while(C>=''&&C<=''){Res=Res*+(C-'');C=getchar();}

     return Res;

 }

 inline void P(int x)

 {

     Num=;if(!x){putchar('');puts("");return;}

     while(x>)CH[++Num]=x%,x/=;

     while(Num)putchar(CH[Num--]+);

     puts("");

 }

 void makeblock()

 {

     sz=sqrt((double)n*log2(n)); if(!sz) sz=;

     for(sum=;sum*sz<n;sum++)

       {

         l[sum]=(sum-)*sz+;

         r[sum]=sum*sz;

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

           num[i]=sum;

       }

     l[sum]=sz*(sum-)+;

     r[sum]=n;

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

       num[i]=sum;

 }

 void makepre()

 {

     for(int i=;i<=n;i++) {pre[i]=pos[a[i]]; pos[a[i]]=i;}

     memcpy(preb,pre,sizeof(pre));

     for(int i=;i<=sum;i++) sort(pre+l[i],pre+r[i]+);

 }

 inline void query()

 {

     int res=;

     if(num[x]+>=num[y]) {for(int i=x;i<=y;i++) if(preb[i]<x) res++;}

     else

       {

           for(int i=x;i<=r[num[x]];i++) if(preb[i]<x) res++;

           for(int i=l[num[y]];i<=y;i++) if(preb[i]<x) res++;

           for(int i=num[x]+;i<num[y];i++) res+=lower_bound(pre+l[i],pre+r[i]+,x)-(pre+l[i]);

       }

     P(res);

 }

 inline void update()

 {

     int t=;

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

       if(a[i]==y)

         {*lower_bound(pre+l[num[i]],pre+r[num[i]],preb[i])=x; preb[i]=x;

         sort(pre+l[num[i]],pre+r[num[i]]+); break;}

     a[]=y;

     for(int i=x-;i>=;i--)

       if(a[i]==y)

         {*lower_bound(pre+l[num[x]],pre+r[num[x]],preb[x])=i; preb[x]=i;

         sort(pre+l[num[x]],pre+r[num[x]]+); break;}

     int t2=a[x]; a[x]=y;

     for(int i=x;i>=;i--)

       if(a[i]==t2)

         {t=i; break;}

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

       if(a[i]==t2)

         {*lower_bound(pre+l[num[i]],pre+r[num[i]],preb[i])=t; preb[i]=t;

         sort(pre+l[num[i]],pre+r[num[i]]+); break;}

 }char op[];

 int main()

 {

     n=G();m=G();

     for(int i=;i<=n;i++) a[i]=G();

     makeblock(); makepre();

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

       {

         scanf("%s",op);x=G();y=G();

           if(op[]=='Q') query();

           else update();

       }

     return ;

 }

巴特西

【分块】bzoj2120 数颜色

最新文章

热门文章