#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#include "cp/debug.h"
#else
#define debug(...)
#endif
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int MOD = (int) 1e9 + 7;
const int INF = 0x3f3f3f3f;
struct Info {
int pref[2]{}, suff[2]{};
int l[2]{}; // l[i] = longest `i` subarray
int cnt[2]{}; // the number of ones
int range{};
Info() {}
Info (int val) {
pref[val] = 1;
suff[val] = 1;
l[val] = 1;
cnt[val] = 1;
range = 1;
}
void set(int val) {
pref[val] = range;
pref[!val] = 0;
suff[val] = range;
suff[!val] = 0;
l[val] = range;
l[!val] = 0;
cnt[val] = range;
cnt[!val] = 0;
}
void reverse() {
swap(pref[0], pref[1]);
swap(suff[0], suff[1]);
swap(l[0], l[1]);
swap(cnt[0], cnt[1]);
assert(cnt[0] + cnt[1] == range);
}
};
Info join(const Info &lhs, const Info &rhs) {
Info ans{};
for (int t = 0; t <= 1; ++t) {
ans.pref[t] = (lhs.pref[t] == lhs.range ? lhs.range + rhs.pref[t] : lhs.pref[t]);
ans.suff[t] = (rhs.suff[t] == rhs.range ? rhs.range + lhs.suff[t] : rhs.suff[t]);
ans.l[t] = max({lhs.l[t], rhs.l[t], lhs.suff[t] + rhs.pref[t]});
ans.cnt[t] = lhs.cnt[t] + rhs.cnt[t];
}
ans.range = lhs.range + rhs.range;
return ans;
}
struct SegmentTree {
int n;
vector<Info> tree;
vector<bool> lazy_rev;
vector<int> lazy_set;
SegmentTree() {}
SegmentTree(int _n): n(1) {
while (n < _n) n *= 2;
tree.resize(n * 2);
lazy_rev.resize(n * 2);
lazy_set.resize(n * 2, -1);
}
void pull(int x) {
tree[x] = join(tree[x * 2], tree[x * 2 + 1]);
}
void build(int x, int l, int r, vector<int> &arr) {
if (l == r) {
tree[x] = Info(arr[l]);
return;
}
int mid = (l + r) >> 1;
build(x * 2, l, mid, arr);
build(x * 2 + 1, mid + 1, r, arr);
pull(x);
}
void push(int x) {
if (!lazy_rev[x] && lazy_set[x] == -1) return;
if (lazy_set[x] != -1) {
int val = lazy_set[x];
lazy_set[x] = -1;
for (int child : {x * 2, x * 2 + 1}) {
lazy_set[child] = val;
lazy_rev[child] = false;
tree[child].set(val);
}
}
if (lazy_rev[x]) {
lazy_rev[x] = !lazy_rev[x];
for (int child : {x * 2, x * 2 + 1}) {
lazy_rev[child] = !lazy_rev[child];
tree[child].reverse();
}
}
}
void set(int x, int l, int r, int u, int v, int val) {
// set all value in range [u..v] to `val`
if (r < u || l > v) return;
if (u <= l && r <= v) {
tree[x].set(val);
lazy_rev[x] = false;
lazy_set[x] = val;
return;
}
int mid = (l + r) >> 1;
push(x);
set(x * 2, l, mid, u, v, val);
set(x * 2 + 1, mid + 1, r, u, v, val);
pull(x);
}
void reverse(int x, int l, int r, int u, int v) {
// reverse all value in range [u..v]
if (r < u || l > v) return;
if (u <= l && r <= v) {
tree[x].reverse();
lazy_rev[x] = !lazy_rev[x];
return;
}
int mid = (l + r) >> 1;
push(x);
reverse(x * 2, l, mid, u, v);
reverse(x * 2 + 1, mid + 1, r, u, v);
pull(x);
}
Info query(int x, int l, int r, int u, int v) {
if (r < u || l > v) return Info{};
if (u <= l && r <= v) return tree[x];
int mid = (l + r) >> 1;
push(x);
Info left = query(x * 2, l, mid, u, v);
Info right = query(x * 2 + 1, mid + 1, r, u, v);
return join(left, right);
}
};
int main() {
ios::sync_with_stdio(false); cin.tie(nullptr);
SegmentTree tree;
int n, q;
cin >> n >> q;
vector<int> arr(n);
for (int i = 0; i < n; ++i) {
cin >> arr[i];
}
tree = SegmentTree(n);
tree.build(1, 0, n - 1, arr);
for (int w = 0; w < q; ++w) {
int type, l, r;
cin >> type >> l >> r;
if (type == 0 || type == 1) {
tree.set(1, 0, n - 1, l, r, type);
} else if (type == 2) {
tree.reverse(1, 0, n - 1, l, r);
} else if (type == 3) {
Info res = tree.query(1 ,0, n - 1, l, r);
cout << res.cnt[1] << '\n';
} else if (type == 4) {
Info res = tree.query(1 ,0, n - 1, l, r);
cout << res.l[1] << '\n';
} else {
assert(false);
}
}
return 0;
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CgojaWZkZWYgTE9DQUwKI2luY2x1ZGUgImNwL2RlYnVnLmgiCiNlbHNlCiNkZWZpbmUgZGVidWcoLi4uKQojZW5kaWYKCgptdDE5OTM3IHJuZyhjaHJvbm86OnN0ZWFkeV9jbG9jazo6bm93KCkudGltZV9zaW5jZV9lcG9jaCgpLmNvdW50KCkpOwoKY29uc3QgaW50IE1PRCA9IChpbnQpIDFlOSArIDc7CmNvbnN0IGludCBJTkYgPSAweDNmM2YzZjNmOwoKc3RydWN0IEluZm8gewogICAgaW50IHByZWZbMl17fSwgc3VmZlsyXXt9OwogICAgaW50IGxbMl17fTsgLy8gbFtpXSA9IGxvbmdlc3QgYGlgIHN1YmFycmF5CiAgICBpbnQgY250WzJde307IC8vIHRoZSBudW1iZXIgb2Ygb25lcwogICAgaW50IHJhbmdle307CiAgICBJbmZvKCkge30KICAgIEluZm8gKGludCB2YWwpIHsKICAgICAgICBwcmVmW3ZhbF0gPSAxOwogICAgICAgIHN1ZmZbdmFsXSA9IDE7CiAgICAgICAgbFt2YWxdID0gMTsKICAgICAgICBjbnRbdmFsXSA9IDE7CiAgICAgICAgcmFuZ2UgPSAxOwogICAgfQogICAgdm9pZCBzZXQoaW50IHZhbCkgewogICAgICAgIHByZWZbdmFsXSA9IHJhbmdlOwogICAgICAgIHByZWZbIXZhbF0gPSAwOwogICAgICAgIHN1ZmZbdmFsXSA9IHJhbmdlOwogICAgICAgIHN1ZmZbIXZhbF0gPSAwOwogICAgICAgIGxbdmFsXSA9IHJhbmdlOwogICAgICAgIGxbIXZhbF0gPSAwOwogICAgICAgIGNudFt2YWxdID0gcmFuZ2U7CiAgICAgICAgY250WyF2YWxdID0gMDsKICAgIH0gICAKICAgIHZvaWQgcmV2ZXJzZSgpIHsKICAgICAgICBzd2FwKHByZWZbMF0sIHByZWZbMV0pOwogICAgICAgIHN3YXAoc3VmZlswXSwgc3VmZlsxXSk7CiAgICAgICAgc3dhcChsWzBdLCBsWzFdKTsKICAgICAgICBzd2FwKGNudFswXSwgY250WzFdKTsKICAgICAgICBhc3NlcnQoY250WzBdICsgY250WzFdID09IHJhbmdlKTsKICAgIH0KfTsKCkluZm8gam9pbihjb25zdCBJbmZvICZsaHMsIGNvbnN0IEluZm8gJnJocykgewogICAgSW5mbyBhbnN7fTsKICAgIGZvciAoaW50IHQgPSAwOyB0IDw9IDE7ICsrdCkgewogICAgICAgIGFucy5wcmVmW3RdID0gKGxocy5wcmVmW3RdID09IGxocy5yYW5nZSA/IGxocy5yYW5nZSArIHJocy5wcmVmW3RdIDogbGhzLnByZWZbdF0pOwogICAgICAgIGFucy5zdWZmW3RdID0gKHJocy5zdWZmW3RdID09IHJocy5yYW5nZSA/IHJocy5yYW5nZSArIGxocy5zdWZmW3RdIDogcmhzLnN1ZmZbdF0pOwogICAgICAgIGFucy5sW3RdID0gbWF4KHtsaHMubFt0XSwgcmhzLmxbdF0sIGxocy5zdWZmW3RdICsgcmhzLnByZWZbdF19KTsKICAgICAgICBhbnMuY250W3RdID0gbGhzLmNudFt0XSArIHJocy5jbnRbdF07CiAgICB9CiAgICBhbnMucmFuZ2UgPSBsaHMucmFuZ2UgKyByaHMucmFuZ2U7CiAgICByZXR1cm4gYW5zOwp9CgpzdHJ1Y3QgU2VnbWVudFRyZWUgewogICAgaW50IG47CiAgICB2ZWN0b3I8SW5mbz4gdHJlZTsKICAgIHZlY3Rvcjxib29sPiBsYXp5X3JldjsKICAgIHZlY3RvcjxpbnQ+IGxhenlfc2V0OwogICAgU2VnbWVudFRyZWUoKSB7fQogICAgU2VnbWVudFRyZWUoaW50IF9uKTogbigxKSB7CiAgICAgICAgd2hpbGUgKG4gPCBfbikgbiAqPSAyOwogICAgICAgIHRyZWUucmVzaXplKG4gKiAyKTsKICAgICAgICBsYXp5X3Jldi5yZXNpemUobiAqIDIpOwogICAgICAgIGxhenlfc2V0LnJlc2l6ZShuICogMiwgLTEpOwogICAgfQogICAgdm9pZCBwdWxsKGludCB4KSB7CiAgICAgICAgdHJlZVt4XSA9IGpvaW4odHJlZVt4ICogMl0sIHRyZWVbeCAqIDIgKyAxXSk7CiAgICB9CiAgICB2b2lkIGJ1aWxkKGludCB4LCBpbnQgbCwgaW50IHIsIHZlY3RvcjxpbnQ+ICZhcnIpIHsKICAgICAgICBpZiAobCA9PSByKSB7CiAgICAgICAgICAgIHRyZWVbeF0gPSBJbmZvKGFycltsXSk7CiAgICAgICAgICAgIHJldHVybjsKICAgICAgICB9CiAgICAgICAgaW50IG1pZCA9IChsICsgcikgPj4gMTsKICAgICAgICBidWlsZCh4ICogMiwgbCwgbWlkLCBhcnIpOwogICAgICAgIGJ1aWxkKHggKiAyICsgMSwgbWlkICsgMSwgciwgYXJyKTsKICAgICAgICBwdWxsKHgpOwogICAgfQogICAgdm9pZCBwdXNoKGludCB4KSB7CiAgICAgICAgaWYgKCFsYXp5X3Jldlt4XSAmJiBsYXp5X3NldFt4XSA9PSAtMSkgcmV0dXJuOwogICAgICAgIGlmIChsYXp5X3NldFt4XSAhPSAtMSkgewogICAgICAgICAgICBpbnQgdmFsID0gbGF6eV9zZXRbeF07CiAgICAgICAgICAgIGxhenlfc2V0W3hdID0gLTE7CiAgICAgICAgICAgIGZvciAoaW50IGNoaWxkIDoge3ggKiAyLCB4ICogMiArIDF9KSB7CiAgICAgICAgICAgICAgICBsYXp5X3NldFtjaGlsZF0gPSB2YWw7CiAgICAgICAgICAgICAgICBsYXp5X3JldltjaGlsZF0gPSBmYWxzZTsKICAgICAgICAgICAgICAgIHRyZWVbY2hpbGRdLnNldCh2YWwpOwogICAgICAgICAgICB9CiAgICAgICAgfQogICAgICAgIGlmIChsYXp5X3Jldlt4XSkgewogICAgICAgICAgICBsYXp5X3Jldlt4XSA9ICFsYXp5X3Jldlt4XTsKICAgICAgICAgICAgZm9yIChpbnQgY2hpbGQgOiB7eCAqIDIsIHggKiAyICsgMX0pIHsKICAgICAgICAgICAgICAgIGxhenlfcmV2W2NoaWxkXSA9ICFsYXp5X3JldltjaGlsZF07CiAgICAgICAgICAgICAgICB0cmVlW2NoaWxkXS5yZXZlcnNlKCk7CiAgICAgICAgICAgIH0KICAgICAgICB9CiAgICB9CiAgICB2b2lkIHNldChpbnQgeCwgaW50IGwsIGludCByLCBpbnQgdSwgaW50IHYsIGludCB2YWwpIHsKICAgICAgICAvLyBzZXQgYWxsIHZhbHVlIGluIHJhbmdlIFt1Li52XSB0byBgdmFsYAogICAgICAgIGlmIChyIDwgdSB8fCBsID4gdikgcmV0dXJuOwogICAgICAgIGlmICh1IDw9IGwgJiYgciA8PSB2KSB7CiAgICAgICAgICAgIHRyZWVbeF0uc2V0KHZhbCk7CiAgICAgICAgICAgIGxhenlfcmV2W3hdID0gZmFsc2U7CiAgICAgICAgICAgIGxhenlfc2V0W3hdID0gdmFsOwogICAgICAgICAgICByZXR1cm47CiAgICAgICAgfQogICAgICAgIGludCBtaWQgPSAobCArIHIpID4+IDE7CiAgICAgICAgcHVzaCh4KTsKICAgICAgICBzZXQoeCAqIDIsIGwsIG1pZCwgdSwgdiwgdmFsKTsKICAgICAgICBzZXQoeCAqIDIgKyAxLCBtaWQgKyAxLCByLCB1LCB2LCB2YWwpOwogICAgICAgIHB1bGwoeCk7CiAgICB9CiAgICB2b2lkIHJldmVyc2UoaW50IHgsIGludCBsLCBpbnQgciwgaW50IHUsIGludCB2KSB7CiAgICAgICAgLy8gcmV2ZXJzZSBhbGwgdmFsdWUgaW4gcmFuZ2UgW3UuLnZdCiAgICAgICAgaWYgKHIgPCB1IHx8IGwgPiB2KSByZXR1cm47CiAgICAgICAgaWYgKHUgPD0gbCAmJiByIDw9IHYpIHsKICAgICAgICAgICAgdHJlZVt4XS5yZXZlcnNlKCk7CiAgICAgICAgICAgIGxhenlfcmV2W3hdID0gIWxhenlfcmV2W3hdOwogICAgICAgICAgICByZXR1cm47CiAgICAgICAgfQogICAgICAgIGludCBtaWQgPSAobCArIHIpID4+IDE7CiAgICAgICAgcHVzaCh4KTsKICAgICAgICByZXZlcnNlKHggKiAyLCBsLCBtaWQsIHUsIHYpOwogICAgICAgIHJldmVyc2UoeCAqIDIgKyAxLCBtaWQgKyAxLCByLCB1LCB2KTsKICAgICAgICBwdWxsKHgpOwogICAgfQogICAgSW5mbyBxdWVyeShpbnQgeCwgaW50IGwsIGludCByLCBpbnQgdSwgaW50IHYpIHsKICAgICAgICBpZiAociA8IHUgfHwgbCA+IHYpIHJldHVybiBJbmZve307CiAgICAgICAgaWYgKHUgPD0gbCAmJiByIDw9IHYpIHJldHVybiB0cmVlW3hdOwogICAgICAgIGludCBtaWQgPSAobCArIHIpID4+IDE7CiAgICAgICAgcHVzaCh4KTsKICAgICAgICBJbmZvIGxlZnQgPSBxdWVyeSh4ICogMiwgbCwgbWlkLCB1LCB2KTsKICAgICAgICBJbmZvIHJpZ2h0ID0gcXVlcnkoeCAqIDIgKyAxLCBtaWQgKyAxLCByLCB1LCB2KTsKICAgICAgICByZXR1cm4gam9pbihsZWZ0LCByaWdodCk7CiAgICB9Cn07CgppbnQgbWFpbigpIHsKICAgIGlvczo6c3luY193aXRoX3N0ZGlvKGZhbHNlKTsgY2luLnRpZShudWxscHRyKTsKICAgIFNlZ21lbnRUcmVlIHRyZWU7CiAgICBpbnQgbiwgcTsKICAgIGNpbiA+PiBuID4+IHE7CiAgICB2ZWN0b3I8aW50PiBhcnIobik7CiAgICBmb3IgKGludCBpID0gMDsgaSA8IG47ICsraSkgewogICAgICAgIGNpbiA+PiBhcnJbaV07CiAgICB9CiAgICB0cmVlID0gU2VnbWVudFRyZWUobik7CiAgICB0cmVlLmJ1aWxkKDEsIDAsIG4gLSAxLCBhcnIpOwogICAgZm9yIChpbnQgdyA9IDA7IHcgPCBxOyArK3cpIHsKICAgICAgICBpbnQgdHlwZSwgbCwgcjsKICAgICAgICBjaW4gPj4gdHlwZSA+PiBsID4+IHI7CiAgICAgICAgaWYgKHR5cGUgPT0gMCB8fCB0eXBlID09IDEpIHsKICAgICAgICAgICAgdHJlZS5zZXQoMSwgMCwgbiAtIDEsIGwsIHIsIHR5cGUpOwogICAgICAgIH0gZWxzZSBpZiAodHlwZSA9PSAyKSB7CiAgICAgICAgICAgIHRyZWUucmV2ZXJzZSgxLCAwLCBuIC0gMSwgbCwgcik7CiAgICAgICAgfSBlbHNlIGlmICh0eXBlID09IDMpIHsKICAgICAgICAgICAgSW5mbyByZXMgPSB0cmVlLnF1ZXJ5KDEgLDAsIG4gLSAxLCBsLCByKTsKICAgICAgICAgICAgY291dCA8PCByZXMuY250WzFdIDw8ICdcbic7CiAgICAgICAgfSBlbHNlIGlmICh0eXBlID09IDQpIHsKICAgICAgICAgICAgSW5mbyByZXMgPSB0cmVlLnF1ZXJ5KDEgLDAsIG4gLSAxLCBsLCByKTsKICAgICAgICAgICAgY291dCA8PCByZXMubFsxXSA8PCAnXG4nOwogICAgICAgIH0gZWxzZSB7CiAgICAgICAgICAgIGFzc2VydChmYWxzZSk7CiAgICAgICAgfQogICAgfQogICAgcmV0dXJuIDA7Cn0K