题目链接：https://ac.nowcoder.com/acm/contest/992/K
题意：给一个大小为1e5的数组，由0 1组成，有两种操作，包括区间修改，将一段区间内的0换成1，1换成0; 区间查询，查询区间内连续1的数量。
思路：区间查询和区间修改，明显可以用线段树来做，我们先分析下复杂度，每次操作复杂度为logn，有m次操作(m<=1e5+1)，那么总复杂度为mlogn，是可行的。
我们用线段树维护什么呢，因为要求区间最多连续1的个数。那么需要维护区间前缀连续0/1的个数fr[0]/fr[1]，区间后缀0/1的个数ba[0]/ba[1]，区间连续0/1个数最大值mx[0]/mx[1]。维护连续0的个数是因为0和1可以相互转换，这样进行更新时就方便不少。懒惰标记lazy可以用异或1来更新，因为更新两次就相当与不更新。
因为维护的元素较多，pushup和pushdown操作就稍微复杂。这题查询的方式是需要学习的，返回区间最大连续1的个数，注意考虑由左区间后缀1和右区间前缀1组合的情况。
详见代码：
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int maxn=100005; struct node{ int l,r,len,fr[2],ba[2],mx[2]; int lazy; }tr[maxn<<2]; int n,m,ans,a[maxn]; void pushup(int v){ if(tr[v<<1].fr[0]==tr[v<<1].len){ tr[v].fr[0]=tr[v<<1].fr[0]+tr[v<<1|1].fr[0]; tr[v].fr[1]=0; } else if(tr[v<<1].fr[1]==tr[v<<1].len){ tr[v].fr[1]=tr[v<<1].fr[1]+tr[v<<1|1].fr[1]; tr[v].fr[0]=0; } else{ tr[v].fr[0]=tr[v<<1].fr[0]; tr[v].fr[1]=tr[v<<1].fr[1]; } if(tr[v<<1|1].ba[0]==tr[v<<1|1].len){ tr[v].ba[0]=tr[v<<1].ba[0]+tr[v<<1|1].ba[0]; tr[v].ba[1]=0; } else if(tr[v<<1|1].ba[1]==tr[v<<1|1].len){ tr[v].ba[1]=tr[v<<1].ba[1]+tr[v<<1|1].ba[1]; tr[v].ba[0]=0; } else{ tr[v].ba[0]=tr[v<<1|1].ba[0]; tr[v].ba[1]=tr[v<<1|1].ba[1]; } tr[v].mx[0]=max(tr[v<<1].ba[0]+tr[v<<1|1].fr[0],max(tr[v<<1].mx[0],tr[v<<1|1].mx[0])); tr[v].mx[1]=max(tr[v<<1].ba[1]+tr[v<<1|1].fr[1],max(tr[v<<1].mx[1],tr[v<<1|1].mx[1])); } void pushdown(int v){ tr[v<<1].lazy^=1,tr[v<<1|1].lazy^=1; swap(tr[v<<1].fr[0],tr[v<<1].fr[1]); swap(tr[v<<1].ba[0],tr[v<<1].ba[1]); swap(tr[v<<1].mx[0],tr[v<<1].mx[1]); swap(tr[v<<1|1].fr[0],tr[v<<1|1].fr[1]); swap(tr[v<<1|1].ba[0],tr[v<<1|1].ba[1]); swap(tr[v<<1|1].mx[0],tr[v<<1|1].mx[1]); tr[v].lazy=0; } void build(int v,int l,int r){ tr[v].l=l,tr[v].r=r,tr[v].len=r-l+1; if(l==r){ if(a[r]){ tr[v].fr[1]=1,tr[v].fr[0]=0; tr[v].ba[1]=1,tr[v].ba[0]=0; tr[v].mx[1]=1,tr[v].mx[0]=0; } else{ tr[v].fr[1]=0,tr[v].fr[0]=1; tr[v].ba[1]=0,tr[v].ba[0]=1; tr[v].mx[1]=0,tr[v].mx[0]=1; } return; } int mid=(l+r)>>1; build(v<<1,l,mid); build(v<<1|1,mid+1,r); pushup(v); } void update(int v,int l,int r){ if(l<=tr[v].l&&r>=tr[v].r){ swap(tr[v].fr[0],tr[v].fr[1]); swap(tr[v].ba[0],tr[v].ba[1]); swap(tr[v].mx[0],tr[v].mx[1]); tr[v].lazy^=1; return; } if(tr[v].lazy) pushdown(v); int mid=(tr[v].l+tr[v].r)>>1; if(l<=mid) update(v<<1,l,r); if(r>mid) update(v<<1|1,l,r); pushup(v); } int query(int v,int l,int r){ if(tr[v].l==l&&tr[v].r==r) return tr[v].mx[1]; if(tr[v].lazy) pushdown(v); int mid=(tr[v].l+tr[v].r)>>1; if(r<=mid) return query(v<<1,l,r); else if(l>mid) return query(v<<1|1,l,r); else{ int x,y,z; x=min(tr[v<<1].ba[1],mid-l+1)+min(tr[v<<1|1].fr[1],r-mid); y=query(v<<1,l,mid); z=query(v<<1|1,mid+1,r); return max(x,max(y,z)); } } int main(){ scanf("%d",&n); for(int i=1;i<=n;++i) scanf("%d",&a[i]); build(1,1,n); scanf("%d",&m); while(m--){ int op,x,y; scanf("%d%d%d",&op,&x,&y); if(op==1) update(1,x,y); else printf("%d ",query(1,x,y)); } return 0; }