给出n个数， 每个数是0或1， 给5种操作， 区间变为1， 区间变为0， 区间0,1翻转， 询问区间内1的个数， 询问区间内最长连续1的个数。
需要将数组开成二维的， 然后区间0， 1翻转只需要交换一个数组的第二维就可以。
一个数组记录区间最长， 一个记录前缀, 一个记录后缀， 一个记录总数， 一个lazy标记， 一个xor标记。
如果遇到覆盖的情况， 那么这个区间如果原先有xor标记， 那么直接将xor清零。
这个题我写的代码可能不太适合人类观看............
#include<bits/stdc++.h>
using namespace std;
#define pb(x) push_back(x)
#define ll long long
#define mk(x, y) make_pair(x, y)
#define lson l, m, rt<<1
#define mem(a) memset(a, 0, sizeof(a))
#define rson m+1, r, rt<<1|1
#define mem1(a) memset(a, -1, sizeof(a))
#define mem2(a) memset(a, 0x3f, sizeof(a))
#define rep(i, a, n) for(int i = a; i<n; i++)
#define ull unsigned long long
typedef pair<int, int> pll;
const double PI = acos(-1.0);
const double eps = 1e-;
const int mod = 1e9+;
const int inf = ;
const int dir[][] = { {-, }, {, }, {, -}, {, } };
const int maxn = 1e5+;
int maxx[maxn<<][], pre_max[maxn<<][], suf_max[maxn<<][], XOR[maxn<<], lazy[maxn<<], sum[maxn<<][];
void pushUp(int rt, int sign, int m) {
maxx[rt][sign] = max(maxx[rt<<][sign], maxx[rt<<|][sign]);
pre_max[rt][sign] = pre_max[rt<<][sign];
suf_max[rt][sign] = suf_max[rt<<|][sign];
sum[rt][sign] = sum[rt<<][sign]+sum[rt<<|][sign];
if(pre_max[rt][sign] == (m-(m>>)))
pre_max[rt][sign] += pre_max[rt<<|][sign];
if(suf_max[rt][sign] == (m>>))
suf_max[rt][sign] += suf_max[rt<<][sign];
maxx[rt][sign] = max(maxx[rt][sign], suf_max[rt<<][sign]+pre_max[rt<<|][sign]);
}
void change(int rt) {
swap(sum[rt][], sum[rt][]);
swap(maxx[rt][], maxx[rt][]);
swap(pre_max[rt][], pre_max[rt][]);
swap(suf_max[rt][], suf_max[rt][]);
XOR[rt]^=;
}
void pushDown(int rt, int m) {
if(~lazy[rt]) {
XOR[rt<<] = XOR[rt<<|] = ;
int sign = lazy[rt];
maxx[rt<<][sign] = sum[rt<<][sign] = pre_max[rt<<][sign] = suf_max[rt<<][sign] = (m-(m>>));
maxx[rt<<|][sign] = sum[rt<<|][sign] = pre_max[rt<<|][sign] = suf_max[rt<<|][sign] = (m>>);
sign^=;
maxx[rt<<][sign] = sum[rt<<][sign] = pre_max[rt<<][sign] = suf_max[rt<<][sign] = ;
maxx[rt<<|][sign] = sum[rt<<|][sign] = pre_max[rt<<|][sign] = suf_max[rt<<|][sign] = ;
lazy[rt<<] = lazy[rt<<|] = lazy[rt];
lazy[rt] = -;
}
if(XOR[rt]) {
change(rt<<);
change(rt<<|);
XOR[rt] = ;
}
}
void build(int l, int r, int rt) {
XOR[rt] = , lazy[rt] = -;
if(l == r) {
int sign;
scanf("%d", &sign);
sum[rt][sign] = pre_max[rt][sign] = suf_max[rt][sign] = maxx[rt][sign] = ;
sign^=;
sum[rt][sign] = pre_max[rt][sign] = suf_max[rt][sign] = maxx[rt][sign] = ;
return ;
}
int m = l+r>>;
build(lson);
build(rson);
pushUp(rt, , r-l+);
pushUp(rt, , r-l+);
}
void update(int L, int R, int l, int r, int rt, int sign) {
if(L<=l&&R>=r) {
if(sign == ) {
change(rt);
} else {
lazy[rt] = sign;
sum[rt][sign] = maxx[rt][sign] = pre_max[rt][sign] = suf_max[rt][sign] = (r-l+);
sign ^= ;
sum[rt][sign] = maxx[rt][sign] = pre_max[rt][sign] = suf_max[rt][sign] = ;
XOR[rt] = ;
}
return ;
}
pushDown(rt, r-l+);
int m = l+r>>;
if(L<=m)
update(L, R, lson, sign);
if(R>m)
update(L, R, rson, sign);
pushUp(rt, , r-l+);
pushUp(rt, , r-l+);
}
int query(int L, int R, int l, int r, int rt, int sign) {
if(L<=l&&R>=r) {
if(sign) {
return maxx[rt][];
} else {
return sum[rt][];
}
}
pushDown(rt, r-l+);
int m = l+r>>, ret = ;
if(sign) {
if(L<=m)
ret = query(L, R, lson, sign);
if(R>m)
ret = max(ret, query(L, R, rson, sign));
ret = max(ret, min(R-m, pre_max[rt<<|][])+min(m-L+, suf_max[rt<<][]));
return ret;
} else {
if(L<=m)
ret += query(L, R, lson, sign);
if(R>m)
ret += query(L, R, rson, sign);
return ret;
}
}
int main()
{
int t, n, m, sign, x, y;
cin>>t;
while(t--) {
scanf("%d%d", &n, &m);
build(, n, );
while(m--) {
scanf("%d%d%d", &sign, &x, &y);
if(sign <= ) {
update(x+, y+, , n, , sign);
} else {
cout<<query(x+, y+, , n, , sign-)<<endl;
}
}
}
}