BZOJ1858 序列操作 （线段树）

题目大意

要求维护一个01序列，要求完成以下几种操作：

0 x y 把区间[x,y]内的数字都变成0 1 x y 把区间[x,y]内的数字都变成1 2 x y 把区间[x,y]内的数字都异或1（取反） 3 x y 询问区间[x,y]内的数字1的个数 4 x y 询问区间[x,y]内最长连续数字1的个数

---

题解

线段数操作，因为有要完成操作4，所以要维护区间最左端和最右端的连续最长的长度。因为有取反操作，所以既要维护关于数字1的信息也要维护数字0的信息。

因为既有取反的标记又有覆盖类的标记，所以要弄清楚两种关系的相互影响。每次执行覆盖类标记的时候应该把反转标记清空，且应该优先执行覆盖类标记。

注意细节吧，挺好写的。

---

代码：

#include <cstdio> #include <iostream> using namespace std; #define ls(k) ((k)<<1) #define rs(k) (ls(k)^1) #define mid ((l+r)>>1) const int maxn=int(1e5)+111; int n; int a[maxn]; struct Node { int len,sum; int l[2],r[2],res[2]; int same,flip; Node():same(-1),flip(0) {} void turn(int k) { l[k]=r[k]=res[k]=len, l[k^1]=r[k^1]=res[k^1]=0; sum=!k?0:len; same=k, flip=0; } void rev() { swap(l[0],l[1]), swap(r[0],r[1]), swap(res[0],res[1]); sum=len-sum; flip^=1; } }node[maxn*4]; void pushdown(int k) { Node &ls=node[ls(k)], &rs=node[rs(k)]; int &same=node[k].same, &flip=node[k].flip; if(same!=-1) { ls.turn(same), rs.turn(same); same=-1; } if(flip==1) { ls.rev(), rs.rev(); flip=0; } } Node maintain(const Node &ls,const Node &rs) { Node R; R.len=ls.len+rs.len, R.sum=ls.sum+rs.sum; for(int i=0;i<2;i++) { R.l[i]=ls.l[i], R.r[i]=rs.r[i]; if(ls.l[i]==ls.len) R.l[i]=ls.len+rs.l[i]; if(rs.r[i]==rs.len) R.r[i]=rs.len+ls.r[i]; R.res[i]=max(max(R.l[i],R.r[i]),ls.r[i]+rs.l[i]); R.res[i]=max(R.res[i],max(ls.res[i],rs.res[i])); } R.same=-1, R.flip=0; return R; } void build(int k,int l,int r) { node[k].len=r-l+1; if(l==r) { int x=a[l]; node[k].l[x]=node[k].r[x]=node[k].res[x]=1; node[k].sum=x; return; } build(ls(k),l,mid); build(rs(k),mid+1,r); node[k]=maintain(node[ls(k)],node[rs(k)]); return; } void cover(int k,int l,int r,int ql,int qr,int col) { if(l!=r) pushdown(k); if(ql<=l && r<=qr) { node[k].turn(col); return; } if(ql<=mid) cover(ls(k),l,mid,ql,qr,col); if(qr> mid) cover(rs(k),mid+1,r,ql,qr,col); node[k]=maintain(node[ls(k)],node[rs(k)]); return; } void cover(int l,int r,int col) { cover(1,1,n,l,r,col); } void flip(int k,int l,int r,int ql,int qr) { if(l!=r) pushdown(k); if(ql<=l && r<=qr) { node[k].rev(); return; } if(ql<=mid) flip(ls(k),l,mid,ql,qr); if(qr> mid) flip(rs(k),mid+1,r,ql,qr); node[k]=maintain(node[ls(k)],node[rs(k)]); return; } void flip(int l,int r) { flip(1,1,n,l,r); } Node query(int k,int l,int r,int ql,int qr) { if(l!=r) pushdown(k); if(ql<=l && r<=qr) return node[k]; if(qr<=mid) return query(ls(k),l,mid,ql,qr); else if(ql>mid) return query(rs(k),mid+1,r,ql,qr); else return maintain(query(ls(k),l,mid,ql,qr),query(rs(k),mid+1,r,ql,qr)); } int query_sum(int l,int r) { Node ans=query(1,1,n,l,r); return ans.sum; } int query_res(int l,int r) { Node ans=query(1,1,n,l,r); return ans.res[1]; } int main() { #ifndef ONLINE_JUDGE freopen("input.txt","r",stdin); freopen("output.txt","w",stdout); #endif // ONLINE_JDUGE int m; scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) scanf("%d",&a[i]); build(1,1,n); for(int t=0;t<m;t++) { int op,x,y; scanf("%d%d%d",&op,&x,&y); x++,y++; if(op==0 || op==1) cover(x,y,op); else if(op==2) flip(x,y); else if(op==3) printf("%d\n",query_sum(x,y)); else if(op==4) printf("%d\n",query_res(x,y)); } return 0; }