bzoj1858: [Scoi2010]序列操作

bzoj1858: [Scoi2010]序列操作 一道裸线段树。的确是比较好想，然而代码写得莫名丑，于是调了很长时间。

---

题解

维护区间中1的总数，左起连续1的个数，右起连续1的个数，最大连续1的个数，0同理。更新的时候左起连续1（0）要考虑左区间全为1（0）延伸到右区间的情况，右起同理。最大连续考虑左区间的右连续+右区间的左连续情况。标记打区间填充和取反。

---

代码

#include<iostream> #include<cstdio> #define mxn 100010 using namespace std; int op,x,y,n,m; bool a[mxn]; struct node {int ll,rr,sum[2],llen[2],rlen[2],mxlen[2],laz;}b[mxn<<2]; void update(int k) { for(int i=0;i<2;i++) { b[k].sum[i]=b[k<<1].sum[i]+b[k<<1|1].sum[i]; b[k].llen[i]=b[k<<1].llen[i],b[k].rlen[i]=b[k<<1|1].rlen[i]; if(b[k<<1].llen[i]==b[k<<1].rr-b[k<<1].ll+1) b[k].llen[i]=b[k<<1].rr-b[k<<1].ll+1+b[k<<1|1].llen[i]; if(b[k<<1|1].rlen[i]==b[k<<1|1].rr-b[k<<1|1].ll+1) b[k].rlen[i]=b[k<<1|1].rr-b[k<<1|1].ll+1+b[k<<1].rlen[i]; b[k].mxlen[i]=b[k<<1].rlen[i]+b[k<<1|1].llen[i]; if(b[k].mxlen[i]<b[k<<1].mxlen[i])b[k].mxlen[i]=b[k<<1].mxlen[i]; if(b[k].mxlen[i]<b[k<<1|1].mxlen[i])b[k].mxlen[i]=b[k<<1|1].mxlen[i]; } b[k].laz=-1; } void pushdown(int k); void build(int k,int l,int r) { b[k].ll=l,b[k].rr=r,b[k].laz=-1; if(l==r) for(int i=0;i<2;i++) b[k].sum[i]=b[k].rlen[i]=b[k].mxlen[i]=b[k].llen[i]=!(a[l]^i); else { int mid=(l+r)>>1; build(k<<1,l,mid); build(k<<1|1,mid+1,r); update(k); } } void mdf(int k,int l,int r,bool v) { if(b[k].ll==l&&b[k].rr==r) { b[k].laz=v; for(int i=0;i<2;i++) b[k].sum[i]=b[k].llen[i]=b[k].rlen[i]=b[k].mxlen[i]=(b[k].rr-b[k].ll+1)*!(v^i); } else { pushdown(k); int mid=(b[k].ll+b[k].rr)>>1; if(l>mid)mdf(k<<1|1,l,r,v); else if(r<=mid)mdf(k<<1,l,r,v); else mdf(k<<1,l,mid,v),mdf(k<<1|1,mid+1,r,v); update(k); } } void rev(int k,int l,int r) { if(b[k].ll==l&&b[k].rr==r) { if(b[k].laz==2)b[k].laz=-1; else if(b[k].laz>=0)b[k].laz^=1; else b[k].laz=2; b[k].sum[0]^=b[k].sum[1]^=b[k].sum[0]^=b[k].sum[1]; b[k].llen[0]^=b[k].llen[1]^=b[k].llen[0]^=b[k].llen[1]; b[k].rlen[0]^=b[k].rlen[1]^=b[k].rlen[0]^=b[k].rlen[1]; b[k].mxlen[0]^=b[k].mxlen[1]^=b[k].mxlen[0]^=b[k].mxlen[1]; } else { pushdown(k); int mid=(b[k].ll+b[k].rr)>>1; if(l>mid)rev(k<<1|1,l,r); else if(r<=mid)rev(k<<1,l,r); else rev(k<<1,l,mid),rev(k<<1|1,mid+1,r); update(k); } } void pushdown(int k) { if(b[k].laz==2) rev(k<<1,b[k<<1].ll,b[k<<1].rr),rev(k<<1|1,b[k<<1|1].ll,b[k<<1|1].rr); else if(b[k].laz>=0) mdf(k<<1,b[k<<1].ll,b[k<<1].rr,b[k].laz),mdf(k<<1|1,b[k<<1|1].ll,b[k<<1|1].rr,b[k].laz); b[k].laz=-1; } int qsum(int k,int l,int r) { if(b[k].ll==l&&b[k].rr==r) return b[k].sum[1]; else { pushdown(k); int mid=(b[k].ll+b[k].rr)>>1; if(l>mid)return qsum(k<<1|1,l,r); else if(r<=mid)return qsum(k<<1,l,r); else return qsum(k<<1,l,mid)+qsum(k<<1|1,mid+1,r); } } int qmax(int k,int l,int r) { if(b[k].ll==l&&b[k].rr==r) return b[k].mxlen[1]; else { pushdown(k); int mid=(b[k].ll+b[k].rr)>>1; if(l>mid)return qmax(k<<1|1,l,r); else if(r<=mid)return qmax(k<<1,l,r); else { int ret1=max(qmax(k<<1,l,mid),qmax(k<<1|1,mid+1,r)), ret2=min(b[k<<1|1].llen[1],r-mid)+min(b[k<<1].rlen[1],mid-l+1); return max(ret1,ret2); } } } int main() { scanf("%d%d",&n,&m); for(int i=0;i<n;i++) scanf("%d",&a[i]); build(1,0,n-1); while(m--) { scanf("%d%d%d",&op,&x,&y); if(op==2)rev(1,x,y); else if(op==3) printf("%d\n",qsum(1,x,y)); else if(op==4) printf("%d\n",qmax(1,x,y)); else mdf(1,x,y,op); } }