首页 > 代码库 > 【分块】bzoj3226 [Sdoi2008]校门外的区间
【分块】bzoj3226 [Sdoi2008]校门外的区间
题解见 ： http://blog.csdn.net/iamzky/article/details/41088151
ORZ ZKY
2个懒标记：是否翻转，覆盖成了什么。
怎么处理一个块上有两个标记的情况呢？
若该块原来没有任何标记，或要打的标记和原本的标记种类相同，则直接打上标记；
若已有翻转标记，再覆盖时则先清除翻转标记，再打上覆盖标记；
若已有覆盖标记，再翻转时，则直接将覆盖标记取反。
So 某个块上同时只会有1个标记。
P.S.分块此题挺快的……
1 #include<cstdio> 2 #include<cstring> 3 using namespace std; 4 #define sz 370 5 const int n=131070; 6 char op[1],cl,cr; 7 int x,y,num[132000],l[sz],r[sz],cov[sz],sum; 8 bool a[132000],spin[sz],goal; 9 void makeblock() 10 { 11 for(sum=1;sum*sz<n;++sum) 12 { 13 l[sum]=r[sum-1]+1; r[sum]=sum*sz; 14 for(int i=l[sum];i<=r[sum];++i) num[i]=sum; 15 } 16 l[sum]=r[sum-1]+1; r[sum]=n; 17 for(int i=l[sum];i<=r[sum];++i) num[i]=sum; 18 memset(cov,-1,sizeof(cov)); 19 } 20 void pushdown(const int &p) 21 { 22 if(cov[p]!=-1) 23 { 24 for(int i=l[p];i<=r[p];i++) a[i]=cov[p]; 25 cov[p]=-1; 26 } 27 else if(spin[p]) 28 { 29 for(int i=l[p];i<=r[p];i++) a[i]^=1; 30 spin[p]=0; 31 } 32 } 33 void update(const int &L,const int &R,const bool &sym) 34 { 35 pushdown(num[L]); pushdown(num[R]); 36 if(num[L]==num[R]) {for(int i=L;i<=R;++i) a[i]=sym;} 37 else 38 { 39 for(int i=L;i<=r[num[L]];++i) a[i]=sym; 40 for(int i=l[num[R]];i<=R;++i) a[i]=sym; 41 for(int i=num[L]+1;i<num[R];++i) {spin[i]=0; cov[i]=sym;} 42 } 43 } 44 void rotate(const int &L,const int &R) 45 { 46 pushdown(num[L]); pushdown(num[R]); 47 if(num[L]==num[R]) {for(int i=L;i<=R;++i) a[i]^=1;} 48 else 49 { 50 for(int i=L;i<=r[num[L]];++i) a[i]^=1; 51 for(int i=l[num[R]];i<=R;++i) a[i]^=1; 52 for(int i=num[L]+1;i<num[R];++i) 53 if(cov[i]==-1) spin[i]^=1; 54 else cov[i]^=1; 55 } 56 } 57 int Ma(const int &v,const char &c) 58 { 59 if(c==‘[‘||c==‘]‘) return (v<<1); 60 else if(c==‘(‘) return (v<<1)+1; 61 else return (v<<1)-1; 62 } 63 int main() 64 { 65 makeblock(); 66 while(scanf("%s %c%d,%d%c",op,&cl,&x,&y,&cr)!=EOF) 67 { 68 if(op[0]==‘U‘) update(Ma(x,cl),Ma(y,cr),1); 69 else if(op[0]==‘I‘) 70 { 71 if(x) update(0,Ma(x,cl)-1,0); 72 if(y!=65535) update(Ma(y,cr)+1,65535<<1,0); 73 } 74 else if(op[0]==‘D‘) update(Ma(x,cl),Ma(y,cr),0); 75 else if(op[0]==‘C‘) 76 { 77 rotate(Ma(x,cl),Ma(y,cr)); 78 if(x) update(0,Ma(x,cl)-1,0); 79 if(y!=65535) update(Ma(y,cr)+1,65535<<1,0); 80 } 81 else rotate(Ma(x,cl),Ma(y,cr)); 82 } 83 int head=0; 84 for(int i=1;i<=sum;++i) pushdown(i); 85 for(int i=0;i<=n;++i) 86 { 87 if(((!i) && a[i]) || (a[i] && (!a[i-1]))) head=i; 88 if((i==n && a[i]) || (a[i] && (!a[i+1]))) 89 { 90 goal=1; 91 if(head&1) putchar(‘(‘); 92 else putchar(‘[‘); 93 printf("%d,",head>>1); 94 if(i&1) {printf("%d",i+1>>1); putchar(‘)‘);} 95 else {printf("%d",i>>1); putchar(‘]‘);} 96 putchar(‘ ‘); 97 } 98 } 99 if(!goal) puts("empty set");100 return 0;101 }
【分块】bzoj3226 [Sdoi2008]校门外的区间
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。