首页 > 代码库 > 【分块】bzoj1593 [Usaco2008 Feb]Hotel 旅馆
【分块】bzoj1593 [Usaco2008 Feb]Hotel 旅馆
分块，记录每个块内包括左端点的最大连续白段的长度，
整个块内的最大连续白段的长度，
和包括右端点的最大连续白段的长度。
Because 是区间染色，所以要打标记。
至于怎样在O(sqrt(n))的时间内找到最左的白色段呢？非常恶心…… 要考虑跨块的白段和块内的白段，并且顺序不能反。(代码中高亮的部分)
这题完全体现不出分块编程复杂度低的优势，完全逊色于线段树。
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 All[300],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 for(int i=1;i<=sum;i++) All[i]=true; 39 } 40 inline bool Is_All(const int &p) 41 {for(int i=l[p];i<=r[p];i++) if(a[i]) return false; return true;} 42 inline void Pushdown(const int &p) 43 { 44 if(delta[p]!=-1) 45 {for(int i=l[p];i<=r[p];i++) a[i]=delta[p]; 46 delta[p]=-1;} 47 } 48 inline void Work(const int &Lb,const int &Rb,const int &sym) 49 { 50 Pushdown(num[Lb]); 51 for(int i=Lb;i<=Rb;i++) a[i]=sym; 52 All[num[Lb]]=Is_All(num[Lb]); 53 int cnt=0; 54 for(int i=l[num[Lb]];i<=r[num[Lb]];i++) {if(a[i]) break; cnt++;} 55 lenl[num[Lb]]=cnt; cnt=0; 56 for(int i=r[num[Lb]];i>=l[num[Lb]];i--) {if(a[i]) break; cnt++;} 57 lenr[num[Lb]]=cnt; cnt=0; 58 int Longest=0; 59 for(int i=l[num[Lb]];i<=r[num[Lb]];i++) 60 { 61 if(a[i]) cnt=0; else cnt++; 62 if(cnt>Longest) Longest=cnt; 63 } 64 len[num[Lb]]=Longest; 65 } 66 inline void Update(const int &L,const int &R,const bool &sym) 67 { 68 if(num[L]==num[R]) Work(L,R,sym); 69 else 70 { 71 Work(L,r[num[L]],sym); 72 Work(l[num[R]],R,sym); 73 for(int i=num[L]+1;i<num[R];i++) 74 { 75 delta[i]=sym; 76 len[i]=lenl[i]=lenr[i]=sym ? 0 : r[i]-l[i]+1; 77 All[i]=sym ? false : true; 78 } 79 } 80 } 81 inline void YuDing() 82 { 83 int kua=0,kuasta; 84 for(int i=1;i<=sum;i++) 85 { 86 if(kua) kua+=lenl[i]; 87 if(kua>=x)//预定sta~sta+x-1 88 { 89 Update(kuasta,kuasta+x-1,true); 90 P(kuasta); 91 return; 92 } 93 if(!All[i]) kua=0; 94 if(!kua&&lenr[i]) 95 { 96 kua=lenr[i]; 97 kuasta=r[i]-lenr[i]+1; 98 } 99 if(len[i]>=x)100 {101 Pushdown(i);102 int cnt=0,Nowleft;103 for(int j=l[i];j<=r[i];j++)104 {105 if(a[j]) cnt=0; else cnt++;106 if(cnt==1) Nowleft=j;107 if(cnt==x)108 {109 Update(Nowleft,Nowleft+x-1,true);110 P(Nowleft);111 return;112 }113 }114 }115 }116 puts("0");117 }118 int main()119 {120 n=G();m=G();121 makeblock();122 for(int i=1;i<=m;i++)123 {124 op=G();x=G();125 if(op==1) YuDing();126 else {y=G(); Update(x,x+y-1,false);}127 }128 return 0;129 }
【分块】bzoj1593 [Usaco2008 Feb]Hotel 旅馆
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。