【分块】bzoj1593 [Usaco2008 Feb]Hotel 旅馆

分块，记录每个块内包括左端点的最大连续白段的长度，

整个块内的最大连续白段的长度，

和包括右端点的最大连续白段的长度。

Because 是区间染色，所以要打标记。

至于怎样在O(sqrt(n))的时间内找到最左的白色段呢？非常恶心…… 要考虑跨块的白段和块内的白段，并且顺序不能反。(代码中YuDing()函数)

这题完全体现不出分块编程复杂度低的优势，完全逊色于线段树。

So 综上，对于要进行复杂的成段修改的题目，分块的编程复杂度较高，几乎没有优势，不推荐写。

  1 #include<cstdio>
  2 #include<cstring>
  3 #include<cmath>
  4 #include<algorithm>
  5 using namespace std;
  6 int len[300],lenl[300],lenr[300],n,m,l[300],r[300],num[50001],sum,sz,x,y;
  7 bool a[50001];
  8 int delta[300],op;
  9 int Res,Num;char C,CH[12];
 10 inline int G()
 11 {
 12     Res=0;C='*'; 
 13     while(C<'0'||C>'9')C=getchar();
 14     while(C>='0'&&C<='9'){Res=Res*10+(C-'0');C=getchar();}
 15     return Res;
 16 }
 17 inline void P(long long x)
 18 {
 19     Num=0;if(!x){putchar('0');puts("");return;}
 20     while(x>0)CH[++Num]=x%10,x/=10;
 21     while(Num)putchar(CH[Num--]+48);
 22     puts("");
 23 }
 24 void makeblock()
 25 {
 26     memset(delta,-1,sizeof(delta));
 27     sz=sqrt(n);
 28     for(sum=1;sum*sz<n;sum++)
 29       {
 30         l[sum]=(sum-1)*sz+1;
 31         r[sum]=sum*sz;
 32         for(int i=l[sum];i<=r[sum];i++) num[i]=sum;
 33         len[sum]=lenl[sum]=lenr[sum]=sz;
 34       }
 35     l[sum]=sz*(sum-1)+1; r[sum]=n;
 36     for(int i=l[sum];i<=r[sum];i++) num[i]=sum;
 37     len[sum]=lenl[sum]=lenr[sum]=r[sum]-l[sum]+1;
 38 }
 39 inline void Pushdown(const int &p)
 40 {
 41     if(delta[p]!=-1)
 42       {for(int i=l[p];i<=r[p];i++) a[i]=delta[p];
 43       delta[p]=-1;}
 44 }
 45 inline void Work(const int &Lb,const int &Rb,const int &sym)
 46 {
 47     Pushdown(num[Lb]);
 48     for(int i=Lb;i<=Rb;i++) a[i]=sym;
 49     int cnt=0;
 50     for(int i=l[num[Lb]];i<=r[num[Lb]];i++) {if(a[i]) break; cnt++;}
 51     lenl[num[Lb]]=cnt; cnt=0;
 52     for(int i=r[num[Lb]];i>=l[num[Lb]];i--) {if(a[i]) break; cnt++;}
 53     lenr[num[Lb]]=cnt; cnt=0;
 54     int Longest=0;
 55     for(int i=l[num[Lb]];i<=r[num[Lb]];i++)
 56       {
 57           if(a[i]) cnt=0; else cnt++;
 58           if(cnt>Longest) Longest=cnt;
 59       }
 60     len[num[Lb]]=Longest;
 61 }
 62 inline void Update(const int &L,const int &R,const bool &sym)
 63 {
 64     if(num[L]==num[R]) Work(L,R,sym);
 65     else
 66       {
 67           Work(L,r[num[L]],sym);
 68           Work(l[num[R]],R,sym);
 69           for(int i=num[L]+1;i<num[R];i++)
 70             {
 71                 delta[i]=sym;
 72                 len[i]=lenl[i]=lenr[i]=sym ? 0 : r[i]-l[i]+1;
 73             }
 74       }
 75 }
 76 inline void YuDing()
 77 {
 78     int kua=0,kuasta;
 79     for(int i=1;i<=sum;i++)
 80       {
 81           if(kua) kua+=lenl[i];
 82         if(kua>=x)//预定sta~sta+x-1 
 83           {
 84               Update(kuasta,kuasta+x-1,true);
 85               P(kuasta);
 86               return;
 87           }
 88           if(len[i]!=r[i]-l[i]+1) kua=0;
 89         if(!kua&&lenr[i])
 90             {
 91                 kua=lenr[i];
 92                 kuasta=r[i]-lenr[i]+1;
 93             }
 94           if(len[i]>=x)
 95           {
 96               Pushdown(i);
 97               int cnt=0,Nowleft;
 98             for(int j=l[i];j<=r[i];j++)
 99               {
100                   if(a[j]) cnt=0; else cnt++;
101                   if(cnt==1) Nowleft=j;
102                   if(cnt==x)
103                     {
104                         Update(Nowleft,Nowleft+x-1,true);
105                         P(Nowleft);
106                         return;
107                     }
108               }
109           }
110       }
111     puts("0");
112 }
113 int main()
114 {
115     n=G();m=G();
116     makeblock();
117     for(int i=1;i<=m;i++)
118       {
119           op=G();x=G();
120           if(op==1) YuDing();
121           else {y=G(); Update(x,x+y-1,false);}
122       }
123     return 0;
124 }