学步园

//HDOJ 3911 Black And White 线段树 区间合并 成段更新

/*
题意：有一堆黑、白球排成一排，有两种操作：
	  1：将一段连续的球改变颜色，黑色变成白色，白色变成黑色
	  2：查询一段区间内连续的黑色的球的个数
	
思路：每个结点记录7个信息：
	  lsum0:从左端开始的连续的白球个数
	  rsum0:从右端开始的连续的白球个数
	  msum0:区间内连续的白球的最大个数
	  lsum1:从左端开始的连续的黑球个数
	  rsum1:从右端开始的连续的黑球个数
	  msum1:区间内连续的黑球的最大个数
	  add:是否向下更新

	  进行操作1的时候只要将黑球白球的各种信息交换	
*/

#include<stdio.h>
#include<string.h>
#include<stdlib.h>

#define N 100005
#define lson rt<<1,l,mid
#define rson rt<<1|1,mid+1,r

int n,m;
int lsum0[N<<2],rsum0[N<<2],msum0[N<<2];
int lsum1[N<<2],rsum1[N<<2],msum1[N<<2];
int sum[N<<2],add[N<<2];

int Max(int x,int y){
	return x>y?x:y;
}

void swap(int &x,int &y){
	int tmp = x;
	x = y;
	y = tmp;
}

void Pushup(int rt,int m){
	lsum0[rt] = lsum0[rt<<1];
	rsum0[rt] = rsum0[rt<<1|1];
	if(lsum0[rt] == m-(m>>1)) lsum0[rt] += lsum0[rt<<1|1];
	if(rsum0[rt] == (m >> 1)) rsum0[rt] += rsum0[rt<<1];
	msum0[rt] = Max(rsum0[rt<<1]+lsum0[rt<<1|1],Max(msum0[rt<<1],msum0[rt<<1|1]));
	
	lsum1[rt] = lsum1[rt<<1];
	rsum1[rt] = rsum1[rt<<1|1];
	if(lsum1[rt] == m-(m>>1)) lsum1[rt] += lsum1[rt<<1|1];
	if(rsum1[rt] == (m >> 1)) rsum1[rt] += rsum1[rt<<1];
	msum1[rt] = Max(rsum1[rt<<1]+lsum1[rt<<1|1],Max(msum1[rt<<1],msum1[rt<<1|1]));
}

void Pushdown(int rt){
	if(add[rt]){
		add[rt<<1] ^= 1;
		add[rt<<1|1] ^= 1;
		swap(lsum0[rt<<1],lsum1[rt<<1]);
		swap(rsum0[rt<<1],rsum1[rt<<1]);
		swap(msum0[rt<<1],msum1[rt<<1]);
		swap(lsum0[rt<<1|1],lsum1[rt<<1|1]);
		swap(rsum0[rt<<1|1],rsum1[rt<<1|1]);
		swap(msum0[rt<<1|1],msum1[rt<<1|1]);
		add[rt] = 0;
	}
}

void Build(int rt,int l,int r){
	if(l == r){
		int x;
		scanf("%d",&x);
		lsum1[rt] = rsum1[rt] = msum1[rt]= x;
		lsum0[rt] = rsum0[rt] = msum0[rt] = 1-x;
		return ;
	}
	int mid = (l + r) >> 1;
	Build(lson);
	Build(rson);
	Pushup(rt,r-l+1);
}

void Update(int rt,int l,int r,int L,int R){
	if(L <= l && R >= r){
		swap(lsum0[rt],lsum1[rt]);
		swap(rsum0[rt],rsum1[rt]);
		swap(msum0[rt],msum1[rt]);
		add[rt]^=1;
		return ;
	}
	Pushdown(rt);
	int mid = (l + r) >> 1;
	if(L <= mid) Update(lson,L,R);
	if(R > mid ) Update(rson,L,R);
	Pushup(rt,r-l+1);
}

int Query(int rt,int l,int r,int L,int R){
	if(L <= l && R >= r){
		return msum1[rt];
	}
	Pushdown(rt);
	int s1=0,s2=0,s3=0;
	int mid = (l + r) >> 1;
	if(L <= mid) s1 = Query(lson,L,R);
	if(R > mid ) s2 = Query(rson,L,R);
	if(L <= mid && R > mid){
		if(rsum1[rt<<1] <= mid-L+1)	s3 += rsum1[rt<<1];
		else						s3 += mid-L+1;
		if(lsum1[rt<<1|1] <= R-mid)	s3 += lsum1[rt<<1|1];
		else						s3 += R-mid;
	}
	return Max(s3,Max(s1,s2));
}

int main(){
	int op,a,b;
	while(scanf("%d",&n)!=EOF){
		memset(lsum0,0,sizeof(lsum0));
		memset(rsum0,0,sizeof(rsum0));
		memset(msum0,0,sizeof(msum0));
		memset(lsum1,0,sizeof(lsum1));
		memset(rsum1,0,sizeof(rsum1));
		memset(msum1,0,sizeof(msum1));
		memset(add,0,sizeof(add));
		Build(1,1,n);
		scanf("%d",&m);
		while(m--){
			scanf("%d %d %d",&op,&a,&b);
			if(op == 1){
				Update(1,1,n,a,b);
			}
			else{
				printf("%d\n",Query(1,1,n,a,b));
			}
		}
	}
	return 0;
}