Problem Description
There are a bunch of stones on the beach; Stone color is white or black. Little Sheep has a magic brush, she can change the color of a continuous stone, black to white, white to black. Little Sheep like black very much, so she want to know the longest period of consecutive black stones in a range [i, j].

Input
There are multiple cases, the first line of each case is an integer n(1<= n <= 10^5), followed by n integer 1 or 0(1 indicates black stone and 0 indicates white stone), then is an integer M(1<=M<=10^5) followed by M operations formatted as x i j(x = 0 or 1) , x=1 means change the color of stones in range[i,j], and x=0 means ask the longest period of consecutive black stones in range[i,j]

Output
When x=0 output a number means the longest length of black stones in range [i,j].

Sample Input
4
1 0 1 0
5
0 1 4
1 2 3
0 1 4
1 3 3
0 4 4

Sample Output
1
2
0

题目链接 ： HDU 3911

这道题目就是叫我们求一个区间最大连续的1的数量，简单用线段树维护一下就行。

用大佬们的话来说就是：*****签到题

可我就是不会，嘤嘤嘤QWQ

题目思路：

区间维护思路：

很明显的维护区间，但是要怎么维护是个问题。

我们可以从题目中很明显的得到，如果一个区间***作次数为偶数就不用管，对吧。

所以我们可以用一个变量来表示当前是偶数次还是奇数次。（就每次异或1嘛，自己想想是不是。）

然后我们再看一下，我们需要的信息，也就是答案，最大连续1的和，怎么去维护。

比如当前我们到了某一个区间，我们想一下，这个区间怎么由两个子区间得到呢？

这个时候有三种情况：

  1. 答案是左区间的最大连续1的和
  2. 答案是右区间的最大连续1的和
  3. 答案是左区间的最大连续靠右1的和 + 答案是右区间的最大连续靠左的1的和

由上面的三种情况我们可以想到，去维护 最大连续靠右1的和 与 最大连续靠左的1的和 ， 这样我们就可以很简单的得到我们想要的答案了。

区间修改维护思路：

虽然我们可以判断奇偶来剪枝，但是我们还是需要真实地去维护这个区间。

怎么维护呢？

刚刚我们记录了关于所有1的信息，如果我们再把0的信息记录一下，当区间需要修改时，交换这两种信息不就可以了吗？

答案查询思路：

怎么去从一个区间查询我们要的信息呢？

这个时候我们要考虑两种情况：

  1. 答案是一个完整的区间
  2. 答案是由两个不完整的区间组合而成

如果答案是完整的区间，我们直接返回这个区间的信息就可以了。
如果答案不是完整区间呢？

这个时候我们想到，上面我们已经记录了，最大连续靠右1的和 与 最大连续靠左的1的和这么重要的信息，同理，我们组合起来求一个最大值不就可以了吗？

但是我们要注意一个问题，比如：
左区间靠右连续1 的和，可能大于我们要查找的这个区间长度，那么我们答案就错了，这个时候，我们需要取个min就可以了。

**最重要的一点：**这道题是多组输入，没多组WA了一次（QAQ）

AC代码：

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n,m;
struct node{
	int l,r,ls,rs,s,col,lazy,ls1,rs1,s1;
}t[N<<2];
void push_up(int p){
	t[p].s=max(t[p<<1].s,max(t[p<<1|1].s,t[p<<1].rs+t[p<<1|1].ls));
	if(t[p<<1].s==t[p<<1].r-t[p<<1].l+1)	t[p].ls=t[p<<1].s+t[p<<1|1].ls;
	if(t[p<<1|1].s==t[p<<1|1].r-t[p<<1|1].l+1)	t[p].rs=t[p<<1|1].s+t[p<<1].rs;
	else	t[p].rs=t[p<<1|1].rs;
	t[p].s1=max(t[p<<1].s1,max(t[p<<1|1].s1,t[p<<1].rs1+t[p<<1|1].ls1));
	if(t[p<<1].s1==t[p<<1].r-t[p<<1].l+1)	t[p].ls1=t[p<<1].s1+t[p<<1|1].ls1;
	else	t[p].ls1=t[p<<1].ls1;
	if(t[p<<1|1].s1==t[p<<1|1].r-t[p<<1|1].l+1)	t[p].rs1=t[p<<1|1].s1+t[p<<1].rs1;
	else	t[p].rs1=t[p<<1|1].rs1;
}
void push_down(int p){
	if(t[p].lazy){
		swap(t[p<<1].s,t[p<<1].s1);	swap(t[p<<1].ls,t[p<<1].ls1);
		swap(t[p<<1].rs,t[p<<1].rs1);	swap(t[p<<1|1].s,t[p<<1|1].s1);
		swap(t[p<<1|1].rs,t[p<<1|1].rs1);	swap(t[p<<1|1].ls,t[p<<1|1].ls1);
		t[p<<1].lazy^=1;	t[p<<1|1].lazy^=1;
		t[p].lazy=0;
	}
}
void build(int p,int l,int r){
	t[p].l=l,t[p].r=r;
	if(l==r){
		scanf("%d",&t[p].col);
		if(t[p].col)	t[p].s=t[p].ls=t[p].rs=1;
		else	t[p].s1=t[p].ls1=t[p].rs1=1;
		return ;
	}
	int mid=l+r>>1;
	build(p<<1,l,mid);	build(p<<1|1,mid+1,r);
	push_up(p);
}
void change(int p,int l,int r){
	if(t[p].l==l&&t[p].r==r){
		swap(t[p].s,t[p].s1);	swap(t[p].ls,t[p].ls1);	swap(t[p].rs,t[p].rs1);
		t[p].lazy^=1;	return ; 
	}
	push_down(p);
	int mid=t[p].l+t[p].r>>1;
	if(r<=mid)	change(p<<1,l,r);
	else if(l>mid)	change(p<<1|1,l,r);
	else	change(p<<1,l,mid),change(p<<1|1,mid+1,r);
	push_up(p);
}
int ask(int p,int l,int r){ 
	if(t[p].l==l&&t[p].r==r)	return t[p].s;
	int mid=t[p].l+t[p].r>>1;
	push_down(p);
	if(r<=mid)	return ask(p<<1,l,r);
	else if(l>mid)	return ask(p<<1|1,l,r);
	else{
		int flag=min(mid-l+1,t[p<<1].rs)+min(r-mid,t[p<<1|1].ls);
		return max(flag,max(ask(p<<1,l,mid),ask(p<<1|1,mid+1,r)));
	}
}
int main(){
	while(~scanf("%d",&n)){
		memset(t,0,sizeof t);
		build(1,1,n);
		scanf("%d",&m);
		while(m--){
			int x,i,j;	scanf("%d %d %d",&x,&i,&j);
			if(x)	change(1,i,j);
			else	printf("%d\n",ask(1,i,j));
		}
	}
	return 0;
}