首页 > 代码库 > BZOJ1858: [Scoi2010]序列操作
BZOJ1858: [Scoi2010]序列操作
1858: [Scoi2010]序列操作
Time Limit: 10 Sec Memory Limit: 64 MBSubmit: 1075 Solved: 552
[Submit][Status]
Description
lxhgww最近收到了一个01序列，序列里面包含了n个数，这些数要么是0，要么是1，现在对于这个序列有五种变换操作和询问操作： 0 a b 把[a, b]区间内的所有数全变成0 1 a b 把[a, b]区间内的所有数全变成1 2 a b 把[a,b]区间内的所有数全部取反，也就是说把所有的0变成1，把所有的1变成0 3 a b 询问[a, b]区间内总共有多少个1 4 a b 询问[a, b]区间内最多有多少个连续的1 对于每一种询问操作，lxhgww都需要给出回答，聪明的程序员们，你们能帮助他吗？
Input
输入数据第一行包括2个数，n和m，分别表示序列的长度和操作数目 第二行包括n个数，表示序列的初始状态 接下来m行，每行3个数，op, a, b，（0<=op<=4，0<=a<=b<n）表示对于区间[a, b]执行标号为op的操作="" <="" div="">
View Code
Output
对于每一个询问操作，输出一行，包括1个数，表示其对应的答案
Sample Input
10 10
0 0 0 1 1 0 1 0 1 1
1 0 2
3 0 5
2 2 2
4 0 4
0 3 6
2 3 7
4 2 8
1 0 5
0 5 6
3 3 9
0 0 0 1 1 0 1 0 1 1
1 0 2
3 0 5
2 2 2
4 0 4
0 3 6
2 3 7
4 2 8
1 0 5
0 5 6
3 3 9
Sample Output
5
2
6
5
2
6
5
HINT
对于30%的数据，1<=n, m<=1000
对于100%的数据，1<=n, m<=100000
Source
Day2
题解：
当涉及多种lazy标记的时候，一定要考虑好各种标记的先后关系
对本题来说：
认为区间赋值为操作1，区间取反为操作2
1.若先 操作2，再操作1，显然2可以不用下传，1覆盖2
2.若先 操作1，再操作2，只需将该节点的tag取反，rev=0，不用下传
3.若只有一种操作，分别执行执行即可
代码：
1 #include<cstdio> 2 #include<cstdlib> 3 #include<cmath> 4 #include<cstring> 5 #include<algorithm> 6 #include<iostream> 7 #include<vector> 8 #include<map> 9 #include<set> 10 #include<queue> 11 #define inf 1000000000 12 #define maxn 100000 13 #define maxm 500+100 14 #define eps 1e-10 15 #define ll long long 16 #define pa pair<int,int> 17 using namespace std; 18 inline int read() 19 { 20 int x=0,f=1;char ch=getchar(); 21 while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();} 22 while(ch>=‘0‘&&ch<=‘9‘){x=10*x+ch-‘0‘;ch=getchar();} 23 return x*f; 24 } 25 struct seg{int l,r,tag,s[2],lx[2],rx[2],mx[2];bool rev;}t[4*maxn]; 26 int n,m,rx,mx; 27 void pushup(int k) 28 { 29 int l=t[k].l,r=t[k].r,mid=(l+r)>>1; 30 for(int i=0;i<=1;i++) 31 { 32 t[k].s[i]=t[k<<1].s[i]+t[k<<1|1].s[i]; 33 t[k].lx[i]=t[k<<1].lx[i]; 34 if(t[k<<1].lx[i]==mid-l+1)t[k].lx[i]+=t[k<<1|1].lx[i]; 35 t[k].rx[i]=t[k<<1|1].rx[i]; 36 if(t[k<<1|1].rx[i]==r-mid)t[k].rx[i]+=t[k<<1].rx[i]; 37 t[k].mx[i]=max(t[k<<1].rx[i]+t[k<<1|1].lx[i],max(t[k<<1].mx[i],t[k<<1|1].mx[i])); 38 } 39 } 40 void build(int k,int x,int y) 41 { 42 int l=t[k].l=x,r=t[k].r=y,mid=(l+r)>>1;t[k].tag=-1;t[k].rev=0; 43 if(l==r) 44 { 45 int z=read(); 46 for(int i=0;i<=1;i++) 47 t[k].s[i]=t[k].lx[i]=t[k].rx[i]=t[k].mx[i]=z==i?1:0; 48 return; 49 } 50 build(k<<1,l,mid);build(k<<1|1,mid+1,r); 51 pushup(k); 52 } 53 void update(int k,int z) 54 { 55 t[k].tag=z; 56 for(int i=0;i<=1;i++) 57 t[k].s[i]=t[k].lx[i]=t[k].rx[i]=t[k].mx[i]=z==i?(t[k].r-t[k].l+1):0; 58 } 59 void solverever(int k) 60 { 61 t[k].rev^=1; 62 swap(t[k].s[0],t[k].s[1]); 63 swap(t[k].lx[0],t[k].lx[1]); 64 swap(t[k].rx[0],t[k].rx[1]); 65 swap(t[k].mx[0],t[k].mx[1]); 66 if(t[k].tag!=-1){t[k].rev=0;t[k].tag^=1;return;} 67 } 68 void pushdown(int k) 69 { 70 if(t[k].tag!=-1) 71 { 72 int z=t[k].tag; 73 update(k<<1,z);update(k<<1|1,z); 74 t[k].tag=-1;t[k].rev=0; 75 } 76 if(t[k].rev) 77 { 78 solverever(k<<1);solverever(k<<1|1); 79 t[k].rev=0; 80 } 81 } 82 void change(int k,int x,int y,int z) 83 { 84 int l=t[k].l,r=t[k].r,mid=(l+r)>>1; 85 if(l==x&&r==y){update(k,z);return;} 86 pushdown(k); 87 if(y<=mid)change(k<<1,x,y,z); 88 else if(x>mid)change(k<<1|1,x,y,z); 89 else change(k<<1,x,mid,z),change(k<<1|1,mid+1,y,z); 90 pushup(k); 91 } 92 void rever(int k,int x,int y) 93 { 94 int l=t[k].l,r=t[k].r,mid=(l+r)>>1; 95 if(l==x&&r==y){solverever(k);return;} 96 pushdown(k); 97 if(y<=mid)rever(k<<1,x,y); 98 else if(x>mid)rever(k<<1|1,x,y); 99 else rever(k<<1,x,mid),rever(k<<1|1,mid+1,y);100 pushup(k);101 }102 int getsum(int k,int x,int y)103 {104 int l=t[k].l,r=t[k].r,mid=(l+r)>>1;105 if(l==x&&r==y)return t[k].s[1];106 pushdown(k);107 if(y<=mid)return getsum(k<<1,x,y);108 else if(x>mid)return getsum(k<<1|1,x,y);109 else return getsum(k<<1,x,mid)+getsum(k<<1|1,mid+1,y); 110 }111 void query(int k,int x,int y)112 {113 int l=t[k].l,r=t[k].r,mid=(l+r)>>1;114 if(l==x&&r==y)115 {116 mx=max(mx,t[k].mx[1]);117 mx=max(mx,rx+t[k].lx[1]);118 if(t[k].s[1]==r-l+1)rx+=t[k].s[1];else rx=t[k].rx[1];119 return;120 }121 pushdown(k);122 if(y<=mid)query(k<<1,x,y);123 else if(x>mid)query(k<<1|1,x,y);124 else query(k<<1,x,mid),query(k<<1|1,mid+1,y);125 }126 int main()127 {128 freopen("input.txt","r",stdin);129 freopen("output.txt","w",stdout);130 n=read();m=read();131 build(1,1,n);132 while(m--)133 {134 int ch=read(),x=read(),y=read();x++;y++;135 switch(ch)136 {137 case 0:change(1,x,y,0);break;138 case 1:change(1,x,y,1);break;139 case 2:rever(1,x,y);break;140 case 3:printf("%d\n",getsum(1,x,y));break;141 case 4:{rx=mx=0;query(1,x,y);printf("%d\n",mx);break;}142 }143 }144 return 0;145 }
BZOJ1858: [Scoi2010]序列操作
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。