Sparse_Table @ 2024-12-11 17:26:19
#include <bits/stdc++.h>
using namespace std;
int n, m;
int a[100005];
struct Tree {
int l, r, lazytag, s0, s1, ls0, ls1, rs0, rs1, as0, as1;
// lazytag : 0 -> 无 1 -> 翻转 2 -> 0 3 -> 1
} tr[100005 << 2];
void pushup(Tree &u, Tree l, Tree r) {
u.s0 = l.s0 + r.s0;
u.s1 = l.s1 + r.s1;
u.ls0 = l.ls0;
if (l.ls0 == l.r - l.l + 1)
u.ls0 += r.ls0;
u.rs0 = r.rs0;
if (r.rs0 == r.r - r.l + 1)
u.rs0 += l.rs0;
u.ls1 = l.ls1;
if (l.ls1 == l.r - l.l + 1)
u.ls1 += r.ls1;
u.rs1 = r.rs1;
if (r.rs1 == r.r - r.l + 1)
u.rs1 += l.rs1;
u.as0 = max({ l.as0, r.as0, l.rs0 + r.ls0 });
u.as1 = max({ l.as1, r.as1, l.rs1 + r.ls1 });
}
void tag(Tree &u, int op) {
int len = u.r - u.l + 1;
if (op == 0)
u.as0 = u.ls0 = u.rs0 = u.s0 = len, u.as1 = u.ls1 = u.rs1 = u.s1 = 0, u.lazytag = 2;
else if (op == 1)
u.as0 = u.ls0 = u.rs0 = u.s0 = 0, u.as1 = u.ls1 = u.rs1 = u.s1 = len, u.lazytag = 3;
else {
swap(u.as0, u.as1);
swap(u.ls0, u.ls1);
swap(u.rs0, u.rs1);
swap(u.s0, u.s1);
u.lazytag ^= 1;
}
}
void pushdown(Tree &u, Tree &l, Tree &r) {
if (u.lazytag) {
int llen = l.r - l.l + 1;
int rlen = r.r - r.l + 1;
l.lazytag = u.lazytag;
r.lazytag = u.lazytag;
if (u.lazytag == 1) {
swap(l.as0, l.as1);
swap(l.ls0, l.ls1);
swap(l.rs0, l.rs1);
swap(l.s0, l.s1);
swap(r.as0, r.as1);
swap(r.ls0, r.ls1);
swap(r.rs0, r.rs1);
swap(r.s0, r.s1);
} else if (u.lazytag == 2) {
l.as0 = l.ls0 = l.rs0 = l.s0 = llen, l.as1 = l.ls1 = l.rs1 = l.s1 = 0;
r.as0 = r.ls0 = r.rs0 = r.s0 = rlen, r.as1 = r.ls1 = r.rs1 = r.s1 = 0;
} else {
l.as0 = l.ls0 = l.rs0 = l.s0 = 0, l.as1 = l.ls1 = l.rs1 = l.s1 = llen;
r.as0 = r.ls0 = r.rs0 = r.s0 = 0, r.as1 = r.ls1 = r.rs1 = r.s1 = rlen;
}
u.lazytag = 0;
}
}
void tag(int u, int op) {
tag(tr[u], op);
}
void pushup(int u) {
pushup(tr[u], tr[u << 1], tr[u << 1 | 1]);
}
void pushdown(int u) {
pushdown(tr[u], tr[u << 1], tr[u << 1 | 1]);
}
void build(int u, int l, int r) {
if (l == r) {
tr[u] = { l, r, 0, !a[l], a[l], !a[l], a[l], !a[l], a[l], !a[l], a[l] };
return;
}
tr[u] = { l, r };
int mid = l + r >> 1;
build(u << 1, l, mid);
build(u << 1 | 1, mid + 1, r);
pushup(u);
}
void modify(int u, int l, int r, int op) {
if (l <= tr[u].l && tr[u].r <= r) {
tag(u, op);
return;
}
pushdown(u);
int mid = tr[u].l + tr[u].r >> 1;
if (l <= mid)
modify(u << 1, l, r, op);
if (r > mid)
modify(u << 1 | 1, l, r, op);
pushup(u);
}
Tree query(int u, int l, int r) {
if (l <= tr[u].l && tr[u].r <= r)
return tr[u];
int mid = tr[u].l + tr[u].r >> 1;
pushdown(u);
Tree ans;
if (r <= mid)
return query(u << 1, l, r);
else if (l > mid)
return query(u << 1 | 1, l, r);
else
pushup(ans, query(u << 1, l, r), query(u << 1 | 1, l, r));
return ans;
}
int main() {
cin >> n >> m;
for (int i = 1; i <= n; i++)
cin >> a[i];
build(1, 1, n);
while (m--) {
int op, x, y;
cin >> op >> x >> y;
x++, y++;
switch (op) {
case 0:
case 1:
case 2:
modify(1, x, y, op);
break;
case 3:
cout << query(1, x, y).s1 << "\n";
break;
case 4:
cout << query(1, x, y).as1 << "\n";
break;
default:
cout << "Error\n";
}
}
return 0;
}