线段树区间翻转，区间找最长连续数字的长度。
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();
}
}
}
京公网安备 11010502036488号