BZOJ 1858 [Scoi2010]序列操作
2017.06.23
题目大意
请维护一个0/1序列，支持以下操作：
- 将编号(a,b)的所有数变为0.
- 将编号(a,b)的所有数变为1.
- 将编号(a,b)的所有数取反.
- 查询编号(a,b)的所有数里有多少个1.
- 查询编号(a,b)的所有数里有多少个连续的1.
这道题涉及到区间操作，那么我们很自然的想到了线段树。
这是一道线段树区间合并的题。
我们想维护这个区间，我们就要看下需要维护哪些性质。
首先维护1的个数（间接维护了0的个数），之后需要维护0和1包含左端点的最长连续长度，包含右端点的最长连续长度和整段区间无特殊要求的最长连续长度。
一共6个维护变量。
对于每次取反我们就可以把所有性质调换进行维护，变0变1直接暴力染色就可以了。
注意这题需要的是Lazy标记的下传冲突问题。
我们在对一个点进行取反操作时，如果发现它已经有染色标记了，我们就把标记取反即可。
#include <bits/stdc++.h>
using namespace std;
int a[100010],n,m,op,inx,iny;
struct segtree
{
int cnt,lazcnt,alen,alenl,alenr,blen,blenl,blenr;
bool change;
}s[500010];
void pushup(int pos,int l,int r)
{
int mid=(l+r)>>1;
s[pos].cnt=s[pos<<1].cnt+s[(pos<<1)|1].cnt;
s[pos].alen=max(max(s[pos<<1].alen,s[(pos<<1)|1].alen),s[pos<<1].alenr+s[(pos<<1)|1].alenl);
if(s[pos<<1].alenl==mid-l+1) s[pos].alenl=s[pos<<1].alenl+s[(pos<<1)|1].alenl;
else s[pos].alenl=s[pos<<1].alenl;
if(s[(pos<<1)|1].alenr==r-mid) s[pos].alenr=s[(pos<<1)|1].alenr+s[pos<<1].alenr;
else s[pos].alenr=s[(pos<<1)|1].alenr;
s[pos].blen=max(max(s[pos<<1].blen,s[(pos<<1)|1].blen),s[pos<<1].blenr+s[(pos<<1)|1].blenl);
if(s[pos<<1].blenl==mid-l+1) s[pos].blenl=s[pos<<1].blenl+s[(pos<<1)|1].blenl;
else s[pos].blenl=s[pos<<1].blenl;
if(s[(pos<<1)|1].blenr==r-mid) s[pos].blenr=s[(pos<<1)|1].blenr+s[pos<<1].blenr;
else s[pos].blenr=s[(pos<<1)|1].blenr;
}
void build(int pos,int l,int r)
{
s[pos].lazcnt=-1;
if(l==r) {s[pos].cnt=a[l];if(a[l]) s[pos].alen++,s[pos].alenl++,s[pos].alenr++;else s[pos].blen++,s[pos].blenl++,s[pos].blenr++;return;}
int mid=(l+r)>>1;
build(pos<<1,l,mid);
build((pos<<1)|1,mid+1,r);
pushup(pos,l,r);
return;
}
void pushdown(int pos,int l,int r)
{
int mid=(l+r)>>1;
if(s[pos].change)
{
s[pos].change=false;
s[pos<<1].change^=1,s[(pos<<1)|1].change^=1;
s[pos<<1].cnt=mid-l+1-s[pos<<1].cnt;
swap(s[pos<<1].alen,s[pos<<1].blen);
swap(s[pos<<1].alenl,s[pos<<1].blenl);
swap(s[pos<<1].alenr,s[pos<<1].blenr);
s[(pos<<1)|1].cnt=r-mid-s[(pos<<1)|1].cnt;
swap(s[(pos<<1)|1].alen,s[(pos<<1)|1].blen);
swap(s[(pos<<1)|1].alenl,s[(pos<<1)|1].blenl);
swap(s[(pos<<1)|1].alenr,s[(pos<<1)|1].blenr);
if(~s[pos<<1].lazcnt) s[pos<<1].lazcnt^=1;
if(~s[(pos<<1)|1].lazcnt) s[(pos<<1)|1].lazcnt^=1;
}
if(s[pos].lazcnt!=-1)
{
s[pos<<1].lazcnt=s[(pos<<1)|1].lazcnt=s[pos].lazcnt;
s[pos].lazcnt=-1;
if(s[pos<<1].lazcnt==0)
{
s[pos<<1].cnt=s[(pos<<1)|1].cnt=0;
s[pos<<1].alen=s[(pos<<1)|1].alen=0;
s[pos<<1].alenl=s[(pos<<1)|1].alenl=0;
s[pos<<1].alenr=s[(pos<<1)|1].alenr=0;
s[pos<<1].blen=s[pos<<1].blenl=s[pos<<1].blenr=mid-l+1;
s[(pos<<1)|1].blen=s[(pos<<1)|1].blenl=s[(pos<<1)|1].blenr=r-mid;
}
if(s[pos<<1].lazcnt==1)
{
s[pos<<1].cnt=s[pos<<1].alen=s[pos<<1].alenl=s[pos<<1].alenr=mid-l+1;
s[(pos<<1)|1].cnt=s[(pos<<1)|1].alen=s[(pos<<1)|1].alenl=s[(pos<<1)|1].alenr=r-mid;
s[pos<<1].blen=s[(pos<<1)|1].blen=0;
s[pos<<1].blenl=s[(pos<<1)|1].blenl=0;
s[pos<<1].blenr=s[(pos<<1)|1].blenr=0;
}
}
}
void update(int pos,int l,int r,int x,int y,int z)
{
int mid=(l+r)>>1;
if(x<=l&&r<=y)
{
if(z==0)
{
s[pos].cnt=0;
s[pos].alen=0;
s[pos].alenl=0;
s[pos].alenr=0;
s[pos].blen=r-l+1;
s[pos].blenl=r-l+1;
s[pos].blenr=r-l+1;
s[pos].lazcnt=0;
}
if(z==1)
{
s[pos].cnt=r-l+1;
s[pos].alen=r-l+1;
s[pos].alenl=r-l+1;
s[pos].alenr=r-l+1;
s[pos].blen=0;
s[pos].blenl=0;
s[pos].blenr=0;
s[pos].lazcnt=1;
}
return;
}
pushdown(pos,l,r);
if(y>mid) update((pos<<1)|1,mid+1,r,x,y,z);
if(x<=mid) update(pos<<1,l,mid,x,y,z);
pushup(pos,l,r);
}
void updateb(int pos,int l,int r,int x,int y)
{
if(x<=l&&r<=y)
{
s[pos].cnt=r-l+1-s[pos].cnt;
swap(s[pos].alen,s[pos].blen);
swap(s[pos].alenl,s[pos].blenl);
swap(s[pos].alenr,s[pos].blenr);
s[pos].change=!s[pos].change;
if(~s[pos].lazcnt) s[pos].lazcnt^=1;
return;
}
pushdown(pos,l,r);
int mid=(l+r)>>1;
if(y>mid) updateb((pos<<1)|1,mid+1,r,x,y);
if(x<=mid) updateb(pos<<1,l,mid,x,y);
pushup(pos,l,r);
}
int querya(int pos,int l,int r,int x,int y)
{
if(x<=l&&r<=y) return s[pos].cnt;
pushdown(pos,l,r);
int mid=(l+r)>>1,res=0;
if(x<=mid) res+=querya(pos<<1,l,mid,x,y);
if(y>mid) res+=querya((pos<<1)|1,mid+1,r,x,y);
return res;
}
int queryb(int pos,int l,int r,int x,int y)
{
if(x<=l&&r<=y) return s[pos].alen;
pushdown(pos,l,r);
int mid=(l+r)>>1,res=0;
if(x<=mid) res=max(res,queryb(pos<<1,l,mid,x,y));
if(y>mid) res=max(res,queryb((pos<<1)|1,mid+1,r,x,y));
return max(res,min(s[pos<<1].alenr,mid-x+1)+min(s[pos<<1|1].alenl,y-mid));
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i) scanf("%d",&a[i]);
build(1,1,n);
while(m--)
{
scanf("%d%d%d",&op,&inx,&iny);
++inx,++iny;
if(op==0) update(1,1,n,inx,iny,0);
if(op==1) update(1,1,n,inx,iny,1);
if(op==2) updateb(1,1,n,inx,iny);
if(op==3) printf("%d\n",querya(1,1,n,inx,iny));
if(op==4) printf("%d\n",queryb(1,1,n,inx,iny));
}
return 0;
}