BZOJ1858: [Scoi2010]序列操作

1858: [Scoi2010]序列操作

Time Limit: 10 Sec Memory Limit: 64 MB
Submit: 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="">

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

Sample Output

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
",getsum(1,x,y));break;
141         case 4:{rx=mx=0;query(1,x,y);printf("%d
",mx);break;}
142         }
143     }
144     return 0;
145 }

View Code