K、白山茶与红玫瑰

线段树区间翻转，区间找最长连续数字的长度。

1、题目要求，区间反转，区间找最长连续1长度。

2、首先想到维护以区间左端点开始的最长连续0/1长度，和从区间右端点开始的最长连续1长度，和这个区间的最长连续1长度。

3、反转操作的话，似乎需要重新来算每一个点，对于线段树来说，显然是不可以接受的，所以我们在维护1的时候，顺带维护一下0，当这个区间需要反转的话，实际上就是0变成1，1变成0，那么我们只需要将这个区间的0和1的三个值交换一下就完成了反转操作。

4、所以现在我们的线段树维护以区间左端点开始的最长连续0/1长度，和从区间右端点开始的最长连续0/1长度，和这个区间的最长连续0/1长度。

5、区间合并

先考虑区间合并后的左端点，首先，它等于左边的子区间的左端点最长连续长度，如果他等于左边子区间的长度，那么还需要加上右边子区间的左端点最长连续长度。

右端点同理。

那么最后，区间的最长连续1长度=max(左子区间右端点+右子区间左端点，左子区间左端点，右子区间右端点，左子区间的最长连续长度，右子区间最长连续1长度)

6、在合并的时候，要注意 左子区间右端点+右子区间左端点，这两个值都是处理过后的，需要先判断一下是否大于他们区间的长度，如果大于区间长度，就取区间长度作为他的值。 

题目链接

Code:

#include <bits/stdc++.h>
#define lson left,mid,k<<1
#define rson mid+1,right,k<<1|1
#define imid int mid=(left+right)/2;
using namespace std;
const int MAXN = 1e5 + 5;
struct node
{
	int l;
	int r;
	int mark;//是否需要反转
	int lm1;//左端点开始的最大值 1
	int lm0;
	int rm1;//右端点开始的最大值 1
	int rm0;
	int mm1;//区间最大值
	int mm0;
}que[MAXN * 4];
int ql, qr, val;
int a[MAXN];
int n, m;
void up(int k)
{
	que[k].lm1 = que[k << 1].lm1;
	if (que[k << 1].lm1 == que[k << 1].r - que[k << 1].l + 1)
		que[k].lm1 += que[k << 1 | 1].lm1;
	que[k].rm1 = que[k << 1 | 1].rm1;
	if (que[k << 1 | 1].rm1 == que[k << 1 | 1].r - que[k << 1 | 1].l + 1)
		que[k].rm1 += que[k << 1].rm1;
	que[k].mm1 = que[k << 1].rm1 + que[k << 1 | 1].lm1;
	que[k].mm1 = max(max(que[k << 1].mm1, que[k << 1 | 1].mm1), que[k].mm1);
	que[k].mm1 = max(max(que[k].lm1, que[k].rm1), que[k].mm1);

	que[k].lm0 = que[k << 1].lm0;
	if (que[k << 1].lm0 == que[k << 1].r - que[k << 1].l + 1)
		que[k].lm0 += que[k << 1 | 1].lm0;
	que[k].rm0 = que[k << 1 | 1].rm0;
	if (que[k << 1 | 1].rm0 == que[k << 1 | 1].r - que[k << 1 | 1].l + 1)
		que[k].rm0 += que[k << 1].rm0;
	que[k].mm0 = que[k << 1].rm0 + que[k << 1 | 1].lm0;
	que[k].mm0 = max(max(que[k << 1].mm0, que[k << 1 | 1].mm0), que[k].mm0);
	que[k].mm0 = max(max(que[k].lm0, que[k].rm0), que[k].mm0);
}
void down(int k)
{
	if (que[k].mark)
	{
		que[k << 1].mark ^= 1;
		swap(que[k << 1].lm1, que[k << 1].lm0);
		swap(que[k << 1].rm1, que[k << 1].rm0);
		swap(que[k << 1].mm1, que[k << 1].mm0);
		que[k << 1 | 1].mark ^= 1;
		swap(que[k << 1 | 1].lm1, que[k << 1 | 1].lm0);
		swap(que[k << 1 | 1].rm1, que[k << 1 | 1].rm0);
		swap(que[k << 1 | 1].mm1, que[k << 1 | 1].mm0);
		que[k].mark = 0;
	}
}
void build(int left = 1, int right = n, int k = 1)
{
	que[k].l = left;
	que[k].r = right;
	que[k].mark = 0;
	if (left == right)
	{
		if (a[left] == 1)
		{
			que[k].lm1 = que[k].rm1 = que[k].mm1 = 1;
			que[k].lm0 = que[k].rm0 = que[k].mm0 = 0;
		}
		else
		{
			que[k].lm1 = que[k].rm1 = que[k].mm1 = 0;
			que[k].lm0 = que[k].rm0 = que[k].mm0 = 1;
		}
		return;
	}
	imid;
	build(lson);
	build(rson);
	up(k);
}
void update(int left = 1, int right = n, int k = 1)
{
	if (qr < left || right < ql)
		return;
	if (ql <= left && right <= qr)
	{
		que[k].mark ^= 1;
		swap(que[k].lm1, que[k].lm0);
		swap(que[k].rm1, que[k].rm0);
		swap(que[k].mm1, que[k].mm0);
		return;
	}
	down(k);
	imid;
	update(lson);
	update(rson);
	up(k);
}
int query(int left = 1, int right = n, int k = 1)
{
	if (qr < left || right < ql)
		return 0;
	if (ql <= left && right <= qr)
		return que[k].mm1;
	down(k);
	imid;
	if (qr <= mid) 
		return query(lson);
	else if (ql > mid) 
		return query(rson);
	else
		return max(max(query(lson), query(rson)), min(que[k << 1].rm1, mid - ql + 1) + min(que[k << 1 | 1].lm1, qr - mid));
}
int main()
{
	scanf("%d", &n);
	for (int i = 1; i <= n; i++)
		scanf("%d", &a[i]);
	build();
	scanf("%d", &m);
	int op, q, w;
	while (m--)
	{
		scanf("%d%d%d", &op, &ql, &qr);
		if (op == 0)
		{
			int ans = query();
			printf("%d\n", ans);
		}
		else
		{
			update();
		}
	}
}