BZOJ 1858 [Scoi2010]序列操作 线段树

题意: 一个01序列，五种操作。 0：给定区间清0 1：给定区间清1 2：给定区间所有元素0变1，1变0 3：给定区间查询1的个数 4：给定区间查询最多连续的1的个数 解析: 裸题，因为有操作4所以考虑上线段树。 因为0可能变成1，，所以需要维护0的相关信息以及1的相关信息。 第一个以及第二个操作直接搞一个覆盖标记即可。 第三个操作上一个翻转标记即可，也就是交换01相关信息。 但是显然覆盖标记的优先级较高，所以覆盖标记可能覆盖掉翻转标记，并且有覆盖标记的时候打翻转标记相当于将覆盖标记取反。 第四个操作维护个sum即可。 第五个操作维护个左连续个数，右连续个数，以及最大连续个数。 其中最大连续个数可能为左区间最大连续，右区间最大连续异或是左区间右连续+右区间左连续。 无脑淦就好了。 代码:

using namespace std;struct node{int l,r;int lcnt[2],rcnt[2],mcnt[2],sum[2];int has_tag,cov,rev;}seg[N<<2];void swapp(int rt){(seg[rt].mcnt[0],seg[rt].mcnt[1]);swap(seg[rt].sum[0],seg[rt].sum[1]);}void pushup(int rt){for(int i=0;i<=1;i++){if(seg[rt<<1].lcnt[i]==seg[rt<<1].r-seg[rt<<1].l+1)seg[rt].lcnt[i]=seg[rt<<1].lcnt[i]+seg[rt<<1|1].lcnt[i];else seg[rt].lcnt[i]=seg[rt<<1].lcnt[i];if(seg[rt<<1|1].rcnt[i]==seg[rt<<1|1].r-seg[rt<<1|1].l+1)seg[rt].rcnt[i]=seg[rt<<1|1].rcnt[i]+seg[rt<<1].rcnt[i];else seg[rt].rcnt[i]=seg[rt<<1|1].rcnt[i];seg[rt].sum[i]=seg[rt<<1].sum[i]+seg[rt<<1|1].sum[i];seg[rt].mcnt[i]=max(seg[rt<<1].mcnt[i],max(seg[rt<<1].rcnt[i]+seg[rt<<1|1].lcnt[i],seg[rt<<1|1].mcnt[i]));}}void pushdown(int rt){if(seg[rt].rev){if(seg[rt<<1].has_tag&&seg[rt<<1].l!=seg[rt<<1].r)seg[rt<<1].cov^=1,swapp(rt<<1);else seg[rt<<1].rev^=1,swapp(rt<<1);if(seg[rt<<1|1].has_tag&&seg[rt<<1|1].l!=seg[rt<<1|1].r)seg[rt<<1|1].cov^=1,swapp(rt<<1|1);else seg[rt<<1|1].rev^=1,swapp(rt<<1|1);seg[rt].rev=0;}if(seg[rt].has_tag){int tmp=seg[rt].cov; seg[rt<<1].sum[tmp]=seg[rt<<1].lcnt[tmp]=seg[rt<<1].rcnt[tmp]=seg[rt<<1].mcnt[tmp]=seg[rt<<1].r-seg[rt<<1].l+1;seg[rt<<1].sum[tmp^1]=seg[rt<<1].lcnt[tmp^1]=seg[rt<<1].rcnt[tmp^1]=seg[rt<<1].mcnt[tmp^1]=0;seg[rt<<1].has_tag=1,seg[rt<<1].cov=tmp;seg[rt<<1|1].sum[tmp]=seg[rt<<1|1].lcnt[tmp]=seg[rt<<1|1].rcnt[tmp]=seg[rt<<1|1].mcnt[tmp]=seg[rt<<1|1].r-seg[rt<<1|1].l+1;seg[rt<<1|1].sum[tmp^1]=seg[rt<<1|1].lcnt[tmp^1]=seg[rt<<1|1].rcnt[tmp^1]=seg[rt<<1|1].mcnt[tmp^1]=0;seg[rt<<1|1].has_tag=1,seg[rt<<1|1].cov=tmp;seg[rt].has_tag=0,seg[rt].cov=0;}}void build(int l,int r,int rt){seg[rt].l=l,seg[rt].r=r;if(l==r){int x;scanf(“%d”,&x);seg[rt].sum[x]=seg[rt].lcnt[x]=seg[rt].rcnt[x]=seg[rt].mcnt[x]=1;return ;}int mid=(l+r)>>1;build(lson);build(rson);pushup(rt);}void update_cov(int v,int L,int R,int l,int r,int rt){if(L<=l&&r<=R){if(seg[rt].rev)seg[rt].rev=0;seg[rt].has_tag=1;seg[rt].cov=v;seg[rt].lcnt[v]=seg[rt].rcnt[v]=seg[rt].mcnt[v]=seg[rt].sum[v]=r-l+1;seg[rt].lcnt[v^1]=seg[rt].rcnt[v^1]=seg[rt].mcnt[v^1]=seg[rt].sum[v^1]=0;return;}int mid=(l+r)>>1;pushdown(rt);if(L<=mid)update_cov(v,L,R,lson);if(R>mid)update_cov(v,L,R,rson);pushup(rt);}void update_rev(int L,int R,int l,int r,int rt){if(L<=l&&r<=R){if(seg[rt].has_tag&&l!=r){seg[rt].cov^=1;swapp(rt);return;}seg[rt].rev^=1;swapp(rt);return;}int mid=(l+r)>>1;pushdown(rt);if(L<=mid)update_rev(L,R,lson);if(R>mid)update_rev(L,R,rson);pushup(rt);}int query_has(int L,int R,int l,int r,int rt){int ret=0;if(L<=l&&r<=R){return seg[rt].sum[1];}int mid=(l+r)>>1;pushdown(rt);if(L<=mid)ret+=query_has(L,R,lson);if(R>mid)ret+=query_has(L,R,rson);return ret;}struct Re{int l,m,r;};Re query_con(int L,int R,int l,int r,int rt){if(L<=l&&r<=R){Re tmp;tmp.l=seg[rt].lcnt[1];tmp.r=seg[rt].rcnt[1];tmp.m=seg[rt].mcnt[1];return tmp;}pushdown(rt);int mid=(l+r)>>1;if(L>mid)return query_con(L,R,rson);else if(R<=mid)return query_con(L,R,lson);else{Re tmp1=query_con(L,mid,lson);Re tmp2=query_con(mid+1,R,rson);Re ret;if(tmp1else if(tmp2else =max(tmp1.m,max(tmp2.m,tmp1.r+tmp2.l)); return ret;}}int n,m;int main(){scanf(“%d%d”,&n,&m);build(1,n,1);for(int i=1;i<=m;i++){int opt,l,r;scanf(“%d%d%d”,&opt,&l,&r);l++,r++; switch(opt){case 0:update_cov(0,l,r,1,n,1);break; case 1:update_cov(1,l,r,1,n,1);break;case 2:update_rev(l,r,1,n,1);break;case 3:printf(“%d\n”,query_has(l,r,1,n,1));break;case 4:Re print=query_con(l,r,1,n,1);printf(“%d\n”,max(print.l,max(print.m,print.r)))}}}

我提着行李，独自一人向远方走去，夕阳将我的身影拉得斜长，