首页 > 代码库 > 【分块】bzoj1858 [Scoi2010]序列操作

【分块】bzoj1858 [Scoi2010]序列操作

分块 Or 线段树 分块的登峰造极之题

每块维护8个值:

包括左端点在内的最长1段;

包括右端点在内的最长1段;

该块内的最长1段;

该块内1的个数;

包括左端点在内的最长0段;//这四个是因为可能有翻转操作,需要swap 0有关的标记 和 1有关的标记

包括右端点在内的最长0段;

该块内的最长0段;

该块内0的个数。

 

2个懒标记:是否翻转,覆盖成了什么。

怎么处理一个块上有两个标记的情况呢?

若该块原来没有任何标记,或要打的标记和原本的标记种类相同,则直接打上标记;

若已有翻转标记,再覆盖时则先清除翻转标记,再打上覆盖标记;

若已有覆盖标记,再翻转时,则直接将覆盖标记取反。

So 某个块上同时只会有1个标记。

 

代码能力题,同样无法体现分块相对于线段树的“代码简介优势”,不推荐写。耗时也多于线段树。

 

P.S.注意取最长段的时候的细节……如下代码中高亮部分。

P.S.P.S.注意Pushdown的时机。

  1 #include<cstdio>  2 #include<cstring>  3 #include<algorithm>  4 #include<cmath>  5 using namespace std;  6 int len[400],lenl[400],lenr[400],n,m,l[400],r[400],num[100001],sum,sz,x,y;  7 bool a[100001];  8 int len0[400],lenl0[400],lenr0[400],sum1[400],sum0[400];  9 int delta[400],op; 10 bool Spin[400]; 11 int Res,Num;char C,CH[12]; 12 inline int G() 13 { 14     Res=0;C=*;  15     while(C<0||C>9)C=getchar(); 16     while(C>=0&&C<=9){Res=Res*10+(C-0);C=getchar();} 17     return Res; 18 } 19 inline void P(long long x) 20 { 21     Num=0;if(!x){putchar(0);puts("");return;} 22     while(x>0)CH[++Num]=x%10,x/=10; 23     while(Num)putchar(CH[Num--]+48); 24     puts(""); 25 } 26 void Pushdown(const int &p) 27 { 28     if(delta[p]!=-1) 29       { 30           for(int i=l[p];i<=r[p];i++) a[i]=delta[p]; 31           delta[p]=-1; 32       } 33     else if(Spin[p]) 34       { 35           for(int i=l[p];i<=r[p];i++) a[i]^=1; 36           Spin[p]=false; 37       } 38 } 39 inline void Work(const int &Lb,const int &Rb,const int &sym) 40 { 41     if(sym==0||sym==1) {for(int i=Lb;i<=Rb;i++) a[i]=sym;} 42     else if(sym==2) {for(int i=Lb;i<=Rb;i++) a[i]^=1;} 43     int cnt=0; 44     for(int i=l[num[Lb]];i<=r[num[Lb]];i++) {if(a[i]) break; cnt++;}//暴力lenl0 45     lenl0[num[Lb]]=cnt; cnt=0; 46     for(int i=r[num[Lb]];i>=l[num[Lb]];i--) {if(a[i]) break; cnt++;}//暴力lenr0 47     lenr0[num[Lb]]=cnt; cnt=0; 48     int Longest=0; 49     for(int i=l[num[Lb]];i<=r[num[Lb]];i++)//暴力len0 50       { 51           if(a[i]) cnt=0; else cnt++; 52           if(cnt>Longest) Longest=cnt; 53       } 54     len0[num[Lb]]=Longest; cnt=0; 55     for(int i=l[num[Lb]];i<=r[num[Lb]];i++) {if(!a[i]) break; cnt++;}//暴力lenl 56     lenl[num[Lb]]=cnt; cnt=0; 57     for(int i=r[num[Lb]];i>=l[num[Lb]];i--) {if(!a[i]) break; cnt++;}//暴力lenr 58     lenr[num[Lb]]=cnt; cnt=0; Longest=0; 59     for(int i=l[num[Lb]];i<=r[num[Lb]];i++)//暴力len 60       { 61           if(!a[i]) cnt=0; else cnt++; 62           if(cnt>Longest) Longest=cnt; 63       } 64     len[num[Lb]]=Longest; cnt=0; 65     for(int i=l[num[Lb]];i<=r[num[Lb]];i++) if(a[i]) cnt++;//暴力sum1  66     sum1[num[Lb]]=cnt; cnt=0; 67     for(int i=l[num[Lb]];i<=r[num[Lb]];i++) if(!a[i]) cnt++;//暴力sum0  68     sum0[num[Lb]]=cnt; 69 } 70 void makeblock() 71 { 72     memset(delta,-1,sizeof(delta)); 73     sz=sqrt(n); 74     for(sum=1;sum*sz<n;sum++) 75       { 76         l[sum]=(sum-1)*sz+1; 77         r[sum]=sum*sz; 78         for(int i=l[sum];i<=r[sum];i++) num[i]=sum; 79         Work(l[sum],r[sum],-1); 80       } 81     l[sum]=sz*(sum-1)+1; r[sum]=n; 82     for(int i=l[sum];i<=r[sum];i++) num[i]=sum; 83     Work(l[sum],r[sum],-1); 84 } 85 inline void Update(const int &L,const int &R,const bool &sym) 86 { 87     Pushdown(num[L]); 88     Pushdown(num[R]); 89     if(num[L]==num[R]) Work(L,R,sym); 90     else 91       { 92           Work(L,r[num[L]],sym); 93           Work(l[num[R]],R,sym); 94           for(int i=num[L]+1;i<num[R];i++) 95             { 96                 if(Spin[i]) Spin[i]=false; delta[i]=sym; 97                 len[i]=lenl[i]=lenr[i]=sum1[i]=sym ? r[i]-l[i]+1 : 0; 98                 len0[i]=lenl0[i]=lenr0[i]=sum0[i]=sym ? 0 : r[i]-l[i]+1; 99             }100       }101 }102 inline void Update_Spin(const int &L,const int &R)103 {104     Pushdown(num[L]);105     Pushdown(num[R]);106     if(num[L]==num[R]) Work(L,R,2);107     else108       {109           Work(L,r[num[L]],2);110           Work(l[num[R]],R,2);111           for(int i=num[L]+1;i<num[R];i++)112             {113                 if(delta[i]==-1) Spin[i]^=1; else delta[i]^=1;114                 swap(sum1[i],sum0[i]);115                 swap(len[i],len0[i]);116                 swap(lenl[i],lenl0[i]);117                 swap(lenr[i],lenr0[i]);118             }119       }120 }121 inline void Query_Sum(const int &L,const int &R)122 {123     int ans=0;124     Pushdown(num[L]);125     Pushdown(num[R]);126     if(num[L]==num[R]) {for(int i=L;i<=R;i++) if(a[i]) ans++;}127     else128       {129           for(int i=L;i<=r[num[L]];i++) if(a[i]) ans++;130           for(int i=l[num[R]];i<=R;i++) if(a[i]) ans++;131           for(int i=num[L]+1;i<num[R];i++) ans+=sum1[i];132       }133     P(ans);134 }135 inline void Query_Len(const int &L,const int &R)136 {137     Pushdown(num[L]);138     Pushdown(num[R]);139     int ans=0,cnt=0;140     if(num[L]==num[R])141       {142           for(int i=L;i<=R;i++)143             {144                 if(a[i]) cnt++; else cnt=0;145                 ans=max(ans,cnt);146             }147           P(ans);148       }149     else150       {151           int kua=0,cntr=0;152         for(int i=r[num[L]];i>=L;i--) {if(!a[i]) break; kua++;}153         for(int i=l[num[R]];i<=R;i++) {if(!a[i]) break; cntr++;}154         for(int i=num[L]+1;i<num[R];i++)155           {156               if(kua) kua+=lenl[i];157             ans=max(ans,kua);158               if(len[i]!=r[i]-l[i]+1) kua=0;159             if(!kua&&lenr[i]) kua=lenr[i];160             ans=max(ans,len[i]);161           }162           for(int i=L;i<=r[num[L]];i++)163             {164                 if(a[i]) cnt++; else cnt=0;165                 ans=max(ans,cnt);166             } cnt=0;167           for(int i=l[num[R]];i<=R;i++)168             {169                 if(a[i]) cnt++; else cnt=0;170                 ans=max(ans,cnt);171             }172         P(max(ans,kua+cntr));173       }174 }175 int main()176 {177     n=G();m=G();178     for(int i=1;i<=n;i++) a[i]=G();179     makeblock();180     for(int i=1;i<=m;i++)181       {182           op=G();x=G();y=G();x++;y++;183           if(op==0) Update(x,y,0);184           else if(op==1) Update(x,y,1);185           else if(op==2) Update_Spin(x,y);186           else if(op==3) Query_Sum(x,y);187           else Query_Len(x,y);188       }189     return 0;190 }

 

【分块】bzoj1858 [Scoi2010]序列操作