线段树的应用，很不错的一道题目。结点属性包括：
（1）n1：1的个数；
（2）c1：连续1的最大个数；
（3）c0：连续0的最大个数；
（4）lc1/lc0：从区间左边开始，连续1/0的最大个数；
（5）rc1/rc0：从区间右边开始，连续1/0的最大个数；
（6）set：置区间为0/1的标记；
（7）flip：0->1, 1->0的标记。
采用延迟更新。每当更新set时，flip就置为false；每当更新flip时，其实就是c1/c0, lc1/lc0, rc1/rc0的交换。
对于询问最长连续1，共包括3种情况：左子树的最长连续1，右子树的最长连续1，以及左子树rc1+右子树lc1（注意有效范围区间）。
/* 3397 */
#include <iostream>
#include <string>
#include <map>
#include <queue>
#include <set>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <climits>
#include <cctype>
using namespace std; #define MAXN 100005
#define lson l, mid, rt<<1
#define rson mid+1, r, rt<<1|1 typedef struct {
int set;
int n1;
int c1, c0;
int lc1, lc0, rc1, rc0;
bool flip;
} node_t; node_t nd[MAXN<<];
int t, n, m, x;
int op; void maintance_set(int op, int len, int rt) {
nd[rt].set = op;
nd[rt].flip = false;
if (op) {
nd[rt].n1 = nd[rt].c1 = nd[rt].lc1 = nd[rt].rc1 = len;
nd[rt].c0 = nd[rt].lc0 = nd[rt].rc0 = ;
} else {
nd[rt].n1 = nd[rt].c1 = nd[rt].lc1 = nd[rt].rc1 = ;
nd[rt].c0 = nd[rt].lc0 = nd[rt].rc0 = len;
}
} void maintance_flip(int len, int rt) {
if (nd[rt].set >= )
nd[rt].set = !nd[rt].set;
else
nd[rt].flip = !nd[rt].flip;
nd[rt].n1 = len-nd[rt].n1;
swap(nd[rt].c0, nd[rt].c1);
swap(nd[rt].lc0, nd[rt].lc1);
swap(nd[rt].rc0, nd[rt].rc1);
} void PushUp(int l, int r, int rt) {
int lb = rt<<;
int rb = rt<<|;
int mid = (l+r)>>; // update the number of 1
nd[rt].n1 = nd[lb].n1 + nd[rb].n1;
// update the longest continuous 1 and 0 in string
nd[rt].c1 = max(
max(nd[lb].c1, nd[rb].c1),
nd[lb].rc1 + nd[rb].lc1
);
nd[rt].c0 = max(
max(nd[lb].c0, nd[rb].c0),
nd[lb].rc0 + nd[rb].lc0
);
// update the longest continuous 1/0 from left
nd[rt].lc1 = nd[lb].lc1;
nd[rt].lc0 = nd[lb].lc0;
if (nd[lb].lc1 == mid-l+)
nd[rt].lc1 += nd[rb].lc1;
if (nd[lb].lc0 == mid-l+)
nd[rt].lc0 += nd[rb].lc0;
// update the longest continuous 1/0 from right
nd[rt].rc1 = nd[rb].rc1;
nd[rt].rc0 = nd[rb].rc0;
if (nd[rb].rc1 == r-mid)
nd[rt].rc1 += nd[lb].rc1;
if (nd[rb].rc0 == r-mid)
nd[rt].rc0 += nd[lb].rc0;
} void PushDown(int l, int r, int rt) {
int lb = rt<<;
int rb = rt<<|;
int mid = (l+r)>>; if (nd[rt].set >= ) {
// maintance_set lson & rson
maintance_set(nd[rt].set, mid-l+, lb);
maintance_set(nd[rt].set, r-mid, rb);
nd[rt].set = -;
}
if (nd[rt].flip) {
// maintance_flip lson & rson
maintance_flip(mid-l+, lb);
maintance_flip(r-mid, rb);
nd[rt].flip = false;
}
} void build(int l, int r, int rt) {
nd[rt].set = -;
nd[rt].flip = false;
if (l == r) {
scanf("%d", &x);
nd[rt].n1 = nd[rt].c1 = nd[rt].lc1 = nd[rt].rc1 = x;
nd[rt].c0 = nd[rt].lc0 = nd[rt].rc0 = !x;
return ;
}
int mid = (l+r)>>;
build(lson);
build(rson);
PushUp(l, r, rt);
} // update to set [L, R] to op
void update1(int L, int R, int l, int r, int rt) {
if (L<=l && R>=r) {
maintance_set(op, r-l+, rt);
return ;
}
int mid = (l+r)>>;
PushDown(l, r, rt);
if (L <= mid)
update1(L, R, lson);
if (R > mid)
update1(L, R, rson);
PushUp(l, r, rt);
} // update to flip [L, R] one
void update2(int L, int R, int l, int r, int rt) {
if (L<=l && R>=r) {
maintance_flip(r-l+, rt);
return ;
}
int mid = (l+r)>>;
PushDown(l, r, rt);
if (L <= mid)
update2(L, R, lson);
if (R > mid)
update2(L, R, rson);
PushUp(l, r, rt);
} // query the sum of 1 in [L, R]
int query3(int L, int R, int l, int r, int rt) {
if (L<=l && R>=r)
return nd[rt].n1;
int mid = (l+r)>>;
PushDown(l, r, rt);
int ret = ;
if (L <= mid)
ret += query3(L, R, lson);
if (R > mid)
ret += query3(L, R, rson);
return ret;
} // query the longest continous 1 in [L, R]
int query4(int L, int R, int l, int r, int rt) {
if (L<=l && R>=r)
return nd[rt].c1;
int mid = (l+r)>>;
PushDown(l, r, rt);
int ret;
if (L > mid) {
return query4(L, R, rson);
} else if (R <= mid) {
return query4(L, R, lson);
} else {
ret = max(
query4(L, R, lson),
query4(L, R, rson)
);
int rc1 = nd[rt<<].rc1;
int lc1 = nd[rt<<|].lc1;
if (rc1 > mid-L+)
rc1 = mid-L+;
if (lc1 > R-mid)
lc1 = R-mid;
ret = max(
rc1 + lc1,
ret
);
}
return ret;
} int main() {
int i, j, k;
int a, b; #ifndef ONLINE_JUDGE
freopen("data.in", "r", stdin);
freopen("data.out", "w", stdout);
#endif scanf("%d", &t);
while (t--) {
scanf("%d %d", &n, &m);
build(, n, );
while (m--) {
scanf("%d %d %d", &op, &a, &b);
++a;
++b;
if (op == ) {
update1(a, b, , n, );
} else if (op == ) {
update1(a, b, , n, );
} else if (op == ) {
update2(a, b, , n, );
} else if (op == ) {
k = query3(a, b, , n, );
printf("%d\n", k);
} else {
k = query4(a, b, , n, );
printf("%d\n", k);
}
}
} return ;
}