MnZn 70pts 求hack

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N = 1e5 + 5;
int n, q, a[N], l[N << 1], r[N << 1], lch[N << 1], rch[N << 1], len[N << 1];
int tag1[N << 1], tag2[N << 1], sum[N << 1], lmx[2][N << 1], rmx[2][N << 1], mx[2][N << 1];

inline void pushup(int x) {
    sum[x] = sum[lch[x]] + sum[rch[x]];
    for (int i = 0; i <= 1; i ++) {
        lmx[i][x] = (mx[i][lch[x]] == len[lch[x]] ? len[lch[x]] + lmx[i][rch[x]] : lmx[i][lch[x]]);
        rmx[i][x] = (mx[i][rch[x]] == len[rch[x]] ? len[rch[x]] + rmx[i][lch[x]] : rmx[i][rch[x]]);
        mx[i][x] = max({lmx[i][x], rmx[i][x], rmx[i][lch[x]] + lmx[i][rch[x]], mx[i][lch[x]], mx[i][rch[x]]});
    }
}

inline void pushdown(int x) {
    if (tag1[x] != -1) {
        tag1[lch[x]] = tag1[rch[x]] = tag1[x], tag2[lch[x]] = tag2[rch[x]] = 0;
        sum[lch[x]] = len[lch[x]] * tag1[x], sum[rch[x]] = len[rch[x]] * tag1[x];
        lmx[tag1[x]][lch[x]] = rmx[tag1[x]][lch[x]] = mx[tag1[x]][lch[x]] = len[lch[x]];
        lmx[tag1[x]][rch[x]] = rmx[tag1[x]][rch[x]] = mx[tag1[x]][rch[x]] = len[rch[x]];
        lmx[tag1[x] ^ 1][lch[x]] = rmx[tag1[x] ^ 1][lch[x]] = mx[tag1[x] ^ 1][lch[x]] = 0;
        lmx[tag1[x] ^ 1][rch[x]] = rmx[tag1[x] ^ 1][rch[x]] = mx[tag1[x] ^ 1][rch[x]] = 0;
    }
    if (tag2[x]) {
        if (tag1[lch[x]] != -1) tag1[lch[x]] ^= 1; else tag2[lch[x]] ^= 1;
        if (tag1[rch[x]] != -1) tag1[rch[x]] ^= 1; else tag2[rch[x]] ^= 1;
        sum[lch[x]] = len[lch[x]] - sum[lch[x]], sum[rch[x]] = len[rch[x]] - sum[rch[x]];
        swap(lmx[0][lch[x]], lmx[1][lch[x]]), swap(lmx[0][rch[x]], lmx[1][rch[x]]);
        swap(rmx[0][lch[x]], rmx[1][lch[x]]), swap(rmx[0][rch[x]], rmx[1][rch[x]]);
        swap(mx[0][lch[x]], mx[1][lch[x]]), swap(mx[0][rch[x]], mx[1][rch[x]]);
    }
    tag1[x] = -1, tag2[x] = 0;
}

inline void Init(int x, int ql, int qr) {
    tag1[x] = -1, tag2[x] = 0;
    l[x] = ql, r[x] = qr, len[x] = qr - ql + 1;
    if (ql == qr) {
        sum[x] = a[ql];
        lmx[a[ql]][x] = rmx[a[ql]][x] = mx[a[ql]][x] = 1;
        lmx[a[ql] ^ 1][x] = rmx[a[ql] ^ 1][x] = mx[a[ql] ^ 1][x] = 0;
        return ;
    }
    int mid = (ql + qr) >> 1;
    lch[x] = (mid << 1), rch[x] = lch[x] + 1;
    Init(lch[x], ql, mid), Init(rch[x], mid + 1, qr);
    pushup(x);
}

inline void Change(int x, int ql, int qr, int opt) {
    if (ql <= l[x] && r[x] <= qr) {
        tag1[x] = opt, tag2[x] = 0, sum[x] = opt * len[x];
        lmx[opt][x] = rmx[opt][x] = mx[opt][x] = len[x];
        lmx[opt ^ 1][x] = rmx[opt ^ 1][x] = mx[opt ^ 1][x] = 0;
        return ;
    }
    pushdown(x);
    if (r[lch[x]] >= ql) Change(lch[x], ql, qr, opt);
    if (l[rch[x]] <= qr) Change(rch[x], ql, qr, opt);
    pushup(x);
}

inline void Xor(int x, int ql, int qr) {
    if (ql <= l[x] && r[x] <= qr) {
        if (tag1[x] != -1) tag1[x] ^= 1; else tag2[x] ^= 1;
        sum[x] = len[x] - sum[x], swap(mx[0][x], mx[1][x]);
        swap(lmx[0][x], lmx[1][x]), swap(rmx[0][x], rmx[1][x]);
        return ;
    }
    pushdown(x);
    if (r[lch[x]] >= ql) Xor(lch[x], ql, qr);
    if (l[rch[x]] <= qr) Xor(rch[x], ql, qr);
    pushup(x);
}

inline int Sum(int x, int ql, int qr) {
    if (ql <= l[x] && r[x] <= qr) return sum[x];
    pushdown(x); int ans = 0;
    if (r[lch[x]] >= ql) ans += Sum(lch[x], ql, qr);
    if (l[rch[x]] <= qr) ans += Sum(rch[x], ql, qr);
    return ans; 
}

inline array<int, 3> Len(int x, int ql, int qr) {
    if (ql <= l[x] && r[x] <= qr)
        return {lmx[1][x], rmx[1][x], mx[1][x]};
    pushdown(x);
    if (r[lch[x]] >= ql && l[rch[x]] <= qr) {
        array<int, 3> ans1 = Len(lch[x], ql, qr);
        array<int, 3> ans2 = Len(rch[x], ql, qr);
        int Ltot = r[lch[x]] - ql + 1, Rtot = qr - l[rch[x]] + 1;
        int Lmx = (ans1[0] == Ltot ? Ltot + ans2[0] : ans1[0]);
        int Rmx = (ans2[1] == Rtot ? Rtot + ans1[1] : ans2[1]);
        int Mx = max({Lmx, Rmx, ans1[1] + ans2[0], ans1[2], ans2[2]});
        return {Lmx, Rmx, Mx};
    }
    if (r[lch[x]] >= ql) return Len(lch[x], ql, qr);
    if (l[rch[x]] <= qr) return Len(rch[x], ql, qr);
}

signed main() {
    cin >> n >> q;
    for (int i = 1; i <= n; i ++) cin >> a[i];
    Init(1, 1, n);
//      
//  for (int j = 1; j < (n << 1); j ++)
//      cout << j << " " << l[j] << " " << r[j] << " " << lmx[0][j] << " " << rmx[0][j] << " " << mx[0][j] << " " << lmx[1][j] << " " << rmx[1][j] << " " << mx[1][j] << endl;
//  cout << "---------------------------" << endl;
//      
    for (int i = 1, opt, L, R; i <= q; i ++) {
        cin >> opt >> L >> R; L ++, R ++;
        if (opt == 0) Change(1, L, R, 0);
        if (opt == 1) Change(1, L, R, 1);
        if (opt == 2) Xor(1, L, R);
        if (opt == 3) cout << Sum(1, L, R) << endl;
        if (opt == 4) {
            array<int, 3> ans = Len(1, L, R);
            cout << ans[2] << endl;
        }
//      
//      for (int j = 1; j < (n << 1); j ++)
//          cout << j << " " << l[j] << " " << r[j] << " " << lmx[0][j] << " " << rmx[0][j] << " " << mx[0][j] << " " << lmx[1][j] << " " << rmx[1][j] << " " << mx[1][j] << endl;
//      cout << "---------------------------" << endl;
//      
    }
    return 0;
}