sinsop90 @ 2022-07-05 11:37:13
#include <bits/stdc++.h>
#define maxn 1000005
using namespace std;
int rev[maxn << 2], tag[maxn << 2], n, T, a[maxn];
struct node {
int left0, left1, middle0, middle1, right0, right1, sum;
node () { left0 = left1 = middle0 = middle1 = right0 = right1 = sum = 0; }
}ansn[maxn << 2];
int ls(int p) {
return p << 1;
}
int rs(int p) {
return p << 1 | 1;
}
void f(int p, int l, int r, int k) {
rev[p] = 0;
ansn[p].sum = k * (r - l + 1);
tag[p] = k;
if(k) {
ansn[p].left0 = ansn[p].right0 = ansn[p].middle0 = 0;
ansn[p].left1 = ansn[p].right1 = ansn[p].middle1 = r - l + 1;
}
else {
ansn[p].left0 = ansn[p].right0 = ansn[p].middle0 = r - l + 1;
ansn[p].left1 = ansn[p].right1 = ansn[p].middle1 = 0;
}
}
void f2(int p, int l, int r) {
rev[p] ^= 1;
ansn[p].sum = (r - l + 1) - ansn[p].sum;
node res = ansn[p];
ansn[p].left1 = res.left0;
ansn[p].left0 = res.left1;
ansn[p].right1 = res.right0;
ansn[p].right0 = res.right1;
ansn[p].middle1 = res.middle0;
ansn[p].middle0 = res.middle1;
}
void pushdown(int p, int l, int r) {
if(tag[p] != -1) {
rev[p] = 0;
int mid = (l + r) >> 1;
f(ls(p), l, mid, tag[p]);
f(rs(p), mid + 1, r, tag[p]);
tag[p] = -1;
}
if(rev[p]) {
int mid = (l + r) >> 1;
f2(ls(p), l, mid);
f2(rs(p), mid + 1, r);
rev[p] = 0;
}
// tag[p] = -1, rev[p] = 0;
}
void pushup(int p, int l, int r) {
int mid = (l + r) >> 1;
ansn[p].sum = ansn[ls(p)].sum + ansn[rs(p)].sum;
if(ansn[ls(p)].left0 == mid - l + 1) ansn[p].left0 = ansn[ls(p)].left0 + ansn[rs(p)].left0;
else ansn[p].left0 = ansn[ls(p)].left0;
if(ansn[rs(p)].right0 == r - mid) ansn[p].right0 = ansn[rs(p)].right0 + ansn[ls(p)].right0;
else ansn[p].right0 = ansn[rs(p)].right0;
if(ansn[ls(p)].left1 == mid - l + 1) ansn[p].left1 = ansn[ls(p)].left1 + ansn[rs(p)].left1;
else ansn[p].left1 = ansn[ls(p)].left1;
if(ansn[rs(p)].right1 == r - mid) ansn[p].right1 = ansn[rs(p)].right1 + ansn[ls(p)].right1;
else ansn[p].right1 = ansn[rs(p)].right1;
ansn[p].middle0 = max(max(ansn[ls(p)].middle0, ansn[rs(p)].middle0), ansn[ls(p)].right0 + ansn[rs(p)].left0);
ansn[p].middle1 = max(max(ansn[ls(p)].middle1, ansn[rs(p)].middle1), ansn[ls(p)].right1 + ansn[rs(p)].left1);
}
void modify(int p, int l, int r, int nl, int nr, int k) {
pushdown(p, l, r);
if(nl <= l && r <= nr) {
f(p, l, r, k);
return;
}
int mid = (l + r) >> 1;
if(nl <= mid) modify(ls(p), l, mid, nl, nr, k);
if(nr > mid) modify(rs(p), mid + 1, r, nl, nr, k);
pushup(p, l, r);
}
void reverse(int p, int l, int r, int nl, int nr) {
pushdown(p, l, r);
if(nl <= l && r <= nr) {
f2(p, l, r);
return;
}
int mid = (l + r) >> 1;
if(nl <= mid) reverse(ls(p), l, mid, nl, nr);
if(nr > mid) reverse(rs(p), mid + 1, r, nl, nr);
pushup(p, l, r);
}
int querysum(int p, int l, int r, int nl, int nr) {
pushdown(p, l, r);
if(nl <= l && r <= nr) return ansn[p].sum;
int mid = (l + r) >> 1, res = 0;
if(nl <= mid) res += querysum(ls(p), l, mid, nl, nr);
if(nr > mid) res += querysum(rs(p), mid + 1, r, nl, nr);
return res;
}
node querynum(int p, int l, int r, int nl, int nr) {
pushdown(p, l, r);
int mid = (l + r) >> 1;
if(nl == l && nr == r) return ansn[p];
if(nl > mid) return querynum(rs(p), mid + 1, r, nl, nr);
else if(nr <= mid) return querynum(ls(p), l, mid, nl, nr);
else {
node res, lef = querynum(ls(p), l, mid, nl, mid), rig = querynum(rs(p), mid + 1, r, mid + 1, nr);
res.sum = lef.sum + rig.sum;
res.left0 = lef.left0, res.left1 = lef.left1;
if(lef.left0 == mid - l + 1) res.left0 += rig.left0;
if(lef.left1 == mid - l + 1) res.left1 += rig.left1;
res.right0 = rig.right0, res.right1 = rig.right1;
if(rig.right0 == r - mid) res.right0 += lef.right0;
if(rig.right1 == r - mid) res.right1 += lef.right1;
res.middle0 = max(max(lef.middle0, rig.middle0), lef.right0 + rig.left0);
res.middle1 = max(max(lef.middle1, rig.middle1), lef.right1 + rig.left1);
return res;
}
}
int main() {
memset(tag, -1, sizeof tag);
scanf("%d%d", &n, &T);
for(int i = 1;i <= n;i++) {
scanf("%d", &a[i]);
modify(1, 1, n + 1, i, i, a[i]);
}
while(T --) {
int op, l, r;
scanf("%d%d%d", &op, &l, &r);
l++, r++;
if(op == 0) modify(1, 1, n + 1, l, r, 0);
if(op == 1) modify(1, 1, n + 1, l, r, 1);
if(op == 2) reverse(1, 1, n + 1, l, r);
if(op == 3) printf("%d\n", querysum(1, 1, n + 1, l, r));
if(op == 4) printf("%d\n", querynum(1, 1, n + 1, l, r).middle1);
}
}