1234567890sjx @ 2024-07-06 22:48:28
bool begmem;
#include <bits/stdc++.h>
#define int long long
using namespace std;
class FastIO {
public:
int read() {
int o = 1, x; char ch;
while (!isdigit(ch = getchar())) {
if (ch == '-') {
o = -1;
}
}
x = ch ^ 48;
while (isdigit(ch = getchar())) {
x = (x << 3) + (x << 1) + (ch ^ 48);
}
return o * x;
}
} ; FastIO io;
void calcqwq();
const int N = 100100, inf = 1e18;
int a[N];
inline int max(int a, int b) { return a > b ? a : b; }
inline int min(int a, int b) { return a < b ? a : b; }
inline void swap(int &a, int &b) { a ^= b ^= a ^= b; }
struct Node {
int l, r, sum0, sum1, zuo0, zuo1, you0, you1, mx0, mx1, rev, tag;
void init(int p) {
l = r = p, rev = 0, tag = -1;
if (a[p] == 0) {
sum0 = 1, sum1 = 0;
zuo0 = 1, zuo1 = 0;
you0 = 1, you1 = 0;
mx0 = 1, mx1 = 0;
} else {
sum0 = 0, sum1 = 1;
zuo0 = 0, zuo1 = 1;
you0 = 0, you1 = 1;
mx0 = 0, mx1 = 1;
}
}
} z[N << 2];
Node operator+(const Node &l, const Node &r) {
Node res;
res.l = l.l, res.r = r.r, res.rev = 0, res.tag = -1;
res.sum0 = l.sum0 + r.sum0, res.sum1 = l.sum1 + r.sum1;
res.mx0 = max({l.mx0, r.mx0, l.you0 + r.zuo0});
res.mx1 = max({l.mx1, r.mx1, l.you1 + r.zuo1});
if (l.r - l.l + 1 == l.zuo0) res.zuo0 = l.r - l.l + 1 + r.zuo0;
if (l.r - l.l + 1 == l.zuo1) res.zuo1 = l.r - l.l + 1 + r.zuo1;
if (r.r - r.l + 1 == r.you0) res.you0 = r.r - r.l + 1 + r.you0;
if (r.r - r.l + 1 == r.you1) res.you1 = r.r - r.l + 1 + r.you1;
return res;
}
void build(int l, int r, int rt) {
if (l == r) return z[rt].init(l);
int mid = l + r >> 1;
build(l, mid, rt << 1), build(mid + 1, r, rt << 1 | 1);
z[rt] = z[rt << 1] + z[rt << 1 | 1];
}
void push_down(int rt) {
if (~z[rt].tag) {
z[rt << 1].tag = z[rt << 1 | 1].tag = z[rt].tag;
z[rt].rev = 0;
if (z[rt << 1].tag == 0) {
z[rt << 1].sum0 = z[rt << 1].r - z[rt << 1].l + 1;
z[rt << 1].mx0 = z[rt << 1].r - z[rt << 1].l + 1;
z[rt << 1].zuo0 = z[rt << 1].r - z[rt << 1].l + 1;
z[rt << 1].you0 = z[rt << 1].r - z[rt << 1].l + 1;
z[rt << 1].sum1 = z[rt << 1].mx1 = z[rt << 1].zuo1 = z[rt << 1].you1 = 0;
} else {
z[rt << 1].sum1 = z[rt << 1].r - z[rt << 1].l + 1;
z[rt << 1].mx1 = z[rt << 1].r - z[rt << 1].l + 1;
z[rt << 1].zuo1 = z[rt << 1].r - z[rt << 1].l + 1;
z[rt << 1].you1 = z[rt << 1].r - z[rt << 1].l + 1;
z[rt << 1].sum0 = z[rt << 1].mx0 = z[rt << 1].zuo0 = z[rt << 1].you0 = 0;
}
if (z[rt << 1 | 1].tag == 0) {
z[rt << 1 | 1].sum0 = z[rt << 1 | 1].r - z[rt << 1 | 1].l + 1;
z[rt << 1 | 1].mx0 = z[rt << 1 | 1].r - z[rt << 1 | 1].l + 1;
z[rt << 1 | 1].zuo0 = z[rt << 1 | 1].r - z[rt << 1 | 1].l + 1;
z[rt << 1 | 1].you0 = z[rt << 1 | 1].r - z[rt << 1 | 1].l + 1;
z[rt << 1 | 1].sum1 = z[rt << 1 | 1].mx1 = z[rt << 1 | 1].zuo1 = z[rt << 1 | 1].you1 = 0;
} else {
z[rt << 1 | 1].sum1 = z[rt << 1 | 1].r - z[rt << 1 | 1].l + 1;
z[rt << 1 | 1].mx1 = z[rt << 1 | 1].r - z[rt << 1 | 1].l + 1;
z[rt << 1 | 1].zuo1 = z[rt << 1 | 1].r - z[rt << 1 | 1].l + 1;
z[rt << 1 | 1].you1 = z[rt << 1 | 1].r - z[rt << 1 | 1].l + 1;
z[rt << 1 | 1].sum0 = z[rt << 1 | 1].mx0 = z[rt << 1 | 1].zuo0 = z[rt << 1 | 1].you0 = 0;
}
z[rt].tag = -1;
}
if (z[rt].rev) {
z[rt].rev = 0;
z[rt << 1].rev ^= 1, z[rt << 1 | 1].rev ^= 1;
if (z[rt << 1].rev) {
swap(z[rt << 1].zuo1, z[rt << 1].zuo0);
swap(z[rt << 1].you1, z[rt << 1].you0);
swap(z[rt << 1].mx0, z[rt << 1].mx1);
swap(z[rt << 1].sum0, z[rt << 1].sum1);
}
if (z[rt << 1 | 1].rev) {
swap(z[rt << 1 | 1].zuo1, z[rt << 1 | 1].zuo0);
swap(z[rt << 1 | 1].you1, z[rt << 1 | 1].you0);
swap(z[rt << 1 | 1].mx0, z[rt << 1 | 1].mx1);
swap(z[rt << 1 | 1].sum0, z[rt << 1 | 1].sum1);
}
}
}
void modify1(int l, int r, int rt, int ll, int rr, int v) {
if (ll <= l && r <= rr) {
if (v == 1) {
z[rt].sum0 = z[rt].mx0 = z[rt].zuo0 = z[rt].you0 = 0;
z[rt].sum1 = z[rt].r - z[rt].l + 1;
z[rt].mx1 = z[rt].r - z[rt].l + 1;
z[rt].zuo1 = z[rt].r - z[rt].l + 1;
z[rt].you1 = z[rt].r - z[rt].l + 1;
} else {
z[rt].sum1 = z[rt].mx1 = z[rt].zuo1 = z[rt].you1 = 0;
z[rt].sum0 = z[rt].r - z[rt].l + 1;
z[rt].mx0 = z[rt].r - z[rt].l + 1;
z[rt].zuo0 = z[rt].r - z[rt].l + 1;
z[rt].you0 = z[rt].r - z[rt].l + 1;
}
return;
}
int mid = l + r >> 1;
push_down(rt);
if (ll <= mid) modify1(l, mid, rt << 1, ll, rr, v);
if (mid < rr) modify1(mid + 1, r, rt << 1 | 1, ll, rr, v);
z[rt] = z[rt << 1] + z[rt << 1 | 1];
}
void modify2(int l, int r, int rt, int ll, int rr) {
if (ll <= l && r <= rr) {
swap(z[rt].zuo1, z[rt].zuo0);
swap(z[rt].you1, z[rt].you0);
swap(z[rt].mx0, z[rt].mx1);
swap(z[rt].sum0, z[rt].sum1);
return;
}
int mid = l + r >> 1;
push_down(rt);
if (ll <= mid) modify2(l, mid, rt << 1, ll, rr);
if (mid < rr) modify2(mid + 1, r, rt << 1 | 1, ll, rr);
z[rt] = z[rt << 1] + z[rt << 1 | 1];
}
Node query(int l, int r, int rt, int ll, int rr) {
if (ll <= l && r <= rr) return z[rt];
int mid = l + r >> 1;
push_down(rt);
if (ll <= mid && mid < rr) return query(l, mid, rt << 1, ll, rr) + query(mid + 1, r, rt << 1 | 1, ll, rr);
if (ll <= mid) return query(l, mid, rt << 1, ll, rr);
return query(mid + 1, r, rt << 1 | 1, ll, rr);
}
signed main() {
atexit(calcqwq);
int n = io.read(), m = io.read();
for (int i = 1; i <= n; ++i) a[i] = io.read();
build(1, n, 1);
while (m--) {
int o = io.read(), l = io.read(), r = io.read();
l++, r++;
if (o <= 1) modify1(1, n, 1, l, r, o);
else if (o == 2) modify2(1, n, 1, l, r);
else if (o == 3) printf("%lld\n", query(1, n, 1, l, r).sum1);
else printf("%lld\n", query(1, n, 1, l, r).mx1);
}
}
bool endmem;
void calcqwq() {
fprintf(stderr, "Memory = %.5lf\n", (&begmem - &endmem) / 1048576.);
}