本文主要是介绍hdu 3911——Black And White，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
线段树
// 1093MS 10568K G++
#include<iostream>
#include<cstdio>
using namespace std;
#define maxn 100005
#define ls (rt<<1)
#define rs (rt<<1|1)
#define mid ((t[rt].l+t[rt].r)>>1)
int n,m;
struct tree
{int l,r;int lc,rc,lval,rval;// 左起颜色 右起颜色 左起长度 右起长度 int w,b; // white最长 black最长 int cover; // 是否是同一种颜色 int lazy; // 延迟标记
}t[maxn<<2];
void pushup(int rt)//向上更新
{t[rt].lc=t[ls].lc, t[rt].lval=t[ls].lval;if(t[ls].cover!=-1&&t[rs].lc==t[ls].cover)t[rt].lval+=t[rs].lval;t[rt].rc=t[rs].rc, t[rt].rval=t[rs].rval;if(t[rs].cover!=-1&&t[ls].rc==t[rs].cover)t[rt].rval+=t[ls].rval;if(t[ls].cover==t[rs].cover)t[rt].cover=t[ls].cover;elset[rt].cover=-1;t[rt].w=max(t[ls].w,t[rs].w);t[rt].b=max(t[ls].b,t[rs].b);if(t[ls].rc==t[rs].lc)if(t[ls].rc==0)t[rt].w=max(t[ls].rval+t[rs].lval,t[rt].w);elset[rt].b=max(t[ls].rval+t[rs].lval,t[rt].b);
}
void init(int rt)//对该节点进行反转操作
{swap(t[rt].b,t[rt].w);t[rt].lc^=1;t[rt].rc^=1;if(t[rt].cover!=-1)t[rt].cover^=1;
}
void pushdown(int rt)//向下更新
{if(t[rt].lazy!=0){init(ls);init(rs);t[rt].lazy=0;t[ls].lazy^=1;t[rs].lazy^=1;return;}
}
void build(int rt,int l,int r)
{t[rt].l=l,t[rt].r=r;t[rt].lazy=0,t[rt].cover=-1;if(l==r){int x;scanf("%d",&x);if(x==1){t[rt].b=1;t[rt].w=0;t[rt].lc=t[rt].rc=1;t[rt].lval=t[rt].rval=1;t[rt].cover=1;}else{t[rt].b=0;t[rt].w=1;t[rt].lc=t[rt].rc=0;t[rt].lval=t[rt].rval=1;t[rt].cover=0;}return;}build(ls,l,mid);build(rs,mid+1,r);pushup(rt);
}
int query(int rt,int l,int r)
{if(l==t[rt].l&&r==t[rt].r)return t[rt].b;pushdown(rt);if(r<=mid)return query(ls,l,r);else if(l>mid)return query(rs,l,r);else{int ans=0;int lb=query(ls,l,mid); int rb=query(rs,mid+1,r); ans=max(lb,rb); if(t[ls].rc==1&&t[rs].lc==1) ans=max(ans,min(mid-l+1,t[ls].rval)+min(r-mid,t[rs].lval)); //防止超出[l,r]的范围 return ans;}
}
void change(int rt,int l,int r)
{if(l==t[rt].l&&r==t[rt].r){t[rt].lazy^=1;init(rt);return ;}pushdown(rt);if(r<=mid)change(ls,l,r);else if(l>mid)change(rs,l,r);else{change(ls,l,mid);change(rs,mid+1,r);}pushup(rt);
}
int main()
{while(~scanf("%d",&n)){build(1,1,n);int x,l,r;scanf("%d",&m);while(m--){scanf("%d%d%d",&x,&l,&r);if(x==0){int ans=query(1,l,r);printf("%d\n",ans);}elsechange(1,l,r);}}return 0;
}
这篇关于hdu 3911——Black And White的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
