【SCOI2010】 序列操作

#include <iostream>
#include <cstdio>
#include <cmath>
#define ll long long
using namespace std;
const ll MAX = 11451419;
struct tree {
    ll left, right, lx1, rx1, zx1, zs1, lx0, rx0, zx0, zs0;
} jd[5000005];
ll q, n, a[5000005], dmax, dmin, aa, bb, cc, bj[5000005];
void gx(ll w) {
    if (bj[w] == 1) {
        jd[w * 2].lx1 = 0, jd[w * 2].rx1 = 0, jd[w * 2].zs1 = 0, jd[w * 2].zx1 = 0;
        jd[w * 2].lx0 = jd[w * 2].right - jd[w * 2].left + 1,
               jd[w * 2].rx0 = jd[w * 2].right - jd[w * 2].left + 1,
               jd[w * 2].zs0 = jd[w * 2].right - jd[w * 2].left + 1,
               jd[w * 2].zx0 = jd[w * 2].right - jd[w * 2].left + 1;
        bj[w * 2] = 1;
        jd[w * 2 + 1].lx1 = 0, jd[w * 2 + 1].rx1 = 0, jd[w * 2 + 1].zs1 = 0, jd[w * 2 + 1].zx1 = 0;
        jd[w * 2 + 1].lx0 = jd[w * 2 + 1].right - jd[w * 2 + 1].left + 1,
                   jd[w * 2 + 1].rx0 = jd[w * 2 + 1].right - jd[w * 2 + 1].left + 1,
                   jd[w * 2 + 1].zs0 = jd[w * 2 + 1].right - jd[w * 2 + 1].left + 1,
                   jd[w * 2 + 1].zx0 = jd[w * 2 + 1].right - jd[w * 2 + 1].left + 1;
        bj[w * 2 + 1] = 1;
    } else if (bj[w] == 2) {
        jd[w * 2].lx1 = jd[w * 2].right - jd[w * 2].left + 1,
               jd[w * 2].rx1 = jd[w * 2].right - jd[w * 2].left + 1,
               jd[w * 2].zs1 = jd[w * 2].right - jd[w * 2].left + 1,
               jd[w * 2].zx1 = jd[w * 2].right - jd[w * 2].left + 1;
        jd[w * 2].lx0 = 0, jd[w * 2].rx0 = 0, jd[w * 2].zs0 = 0, jd[w * 2].zx0 = 0;
        bj[w * 2] = 2;
        jd[w * 2 + 1].lx1 = jd[w * 2 + 1].right - jd[w * 2 + 1].left + 1,
                   jd[w * 2 + 1].rx1 = jd[w * 2 + 1].right - jd[w * 2 + 1].left + 1,
                   jd[w * 2 + 1].zs1 = jd[w * 2 + 1].right - jd[w * 2 + 1].left + 1,
                   jd[w * 2 + 1].zx1 = jd[w * 2 + 1].right - jd[w * 2 + 1].left + 1;
        jd[w * 2 + 1].lx0 = 0, jd[w * 2 + 1].rx0 = 0, jd[w * 2 + 1].zs0 = 0, jd[w * 2 + 1].zx0 = 0;
        bj[w * 2 + 1] = 2;
    } else if (bj[w] == 3) {
        swap(jd[w * 2].lx0, jd[w * 2].lx1), swap(jd[w * 2].rx0, jd[w * 2].rx1),
            swap(jd[w * 2].zs0, jd[w * 2].zs1), swap(jd[w * 2].zx0, jd[w * 2].zx1);
        bj[w * 2] = (bj[w * 2] == 3) ? 0 : (bj[w * 2] == 0) ? 3 : (bj[w * 2] == 1) ? 2 : 1;
        swap(jd[w * 2 + 1].lx0, jd[w * 2 + 1].lx1), swap(jd[w * 2 + 1].rx0, jd[w * 2 + 1].rx1),
            swap(jd[w * 2 + 1].zs0, jd[w * 2 + 1].zs1), swap(jd[w * 2 + 1].zx0, jd[w * 2 + 1].zx1);
        bj[w * 2 + 1] = (bj[w * 2 + 1] == 3) ? 0 : (bj[w * 2 + 1] == 0) ? 3 : (bj[w * 2 + 1] == 1) ? 2 : 1;
    }
    bj[w] = 0;
}
void js(ll w, ll l, ll r) {
    jd[w].left = l, jd[w].right = r;
    if (l == r) {
        jd[w].lx1 = jd[w].rx1 = jd[w].zx1 = jd[w].zs1 = a[l],
        jd[w].lx0 = jd[w].rx0 = jd[w].zx0 = jd[w].zs0 = !a[l];
        return;
    }
    ll mid = (l + r) >> 1;
    js(w * 2, l, mid);
    js(w * 2 + 1, mid + 1, r);
    jd[w].zs1 = jd[w * 2].zs1 + jd[w * 2 + 1].zs1;
    jd[w].lx1 = max(max(jd[w * 2].lx1, jd[w * 2 + 1].lx1), jd[w * 2].rx1 + jd[w * 2 + 1].zx1);
    jd[w].zx1 = (jd[w * 2].zx1 == jd[w * 2].right - jd[w * 2].left + 1) ? jd[w * 2].zx1 + jd[w * 2 + 1].zx1
                                                                        : jd[w * 2].zx1;
    jd[w].rx1 = (jd[w * 2 + 1].rx1 == jd[w * 2 + 1].right - jd[w * 2 + 1].left + 1)
                    ? jd[w * 2 + 1].rx1 + jd[w * 2].rx1
                    : jd[w * 2 + 1].rx1;
    jd[w].zs0 = jd[w * 2].zs0 + jd[w * 2 + 1].zs0;
    jd[w].lx0 = max(max(jd[w * 2].lx0, jd[w * 2 + 1].lx0), jd[w * 2].rx0 + jd[w * 2 + 0].zx0);
    jd[w].zx0 = (jd[w * 2].zx0 == jd[w * 2].right - jd[w * 2].left + 1) ? jd[w * 2].zx0 + jd[w * 2 + 1].zx0
                                                                        : jd[w * 2].zx0;
    jd[w].rx0 = (jd[w * 2 + 1].rx0 == jd[w * 2 + 1].right - jd[w * 2 + 1].left + 1)
                    ? jd[w * 2 + 1].rx0 + jd[w * 2].rx0
                    : jd[w * 2 + 1].rx0;
}
ll czs(ll w, ll l, ll r) {
    if (jd[w].left >= l && jd[w].right <= r) {
        return jd[w].zs1;
    }
    if (bj[w])
        gx(w);
    if (r <= jd[w * 2].right) {
        return czs(w * 2, l, r);
    } else if (l >= jd[w * 2 + 1].left) {
        return czs(w * 2 + 1, l, r);
    } else {
        return czs(w * 2, l, r) + czs(w * 2 + 1, l, r);
    }
}
ll clx(ll w, ll l, ll r) {
    if (jd[w].left >= l && jd[w].right <= r) {
        return jd[w].lx1;
    }
    if (bj[w])
        gx(w);
    if (r <= jd[w * 2].right) {
        return clx(w * 2, l, r);
    } else if (l >= jd[w * 2 + 1].left) {
        return clx(w * 2 + 1, l, r);
    } else {
        ll re =
            min(jd[w * 2].right - l + 1, jd[w * 2].rx1) + min(r - jd[w * 2 + 1].left + 1, jd[w * 2 + 1].zx1);
        re = max(re, clx(w * 2 + 1, jd[w * 2 + 1].left, r));
        re = max(re, clx(w * 2, l, jd[w * 2].right));
        return re;
    }
}
inline void gj(ll w) {
    if (jd[w].left >= bb && jd[w].right <= cc) {
        if (aa == 0) {
            jd[w].lx1 = 0, jd[w].rx1 = 0, jd[w].zs1 = 0, jd[w].zx1 = 0;
            jd[w].lx0 = jd[w].right - jd[w].left + 1, jd[w].rx0 = jd[w].right - jd[w].left + 1,
            jd[w].zs0 = jd[w].right - jd[w].left + 1, jd[w].zx0 = jd[w].right - jd[w].left + 1;
            bj[w] = 1;
        } else if (aa == 1) {
            jd[w].lx1 = jd[w].right - jd[w].left + 1, jd[w].rx1 = jd[w].right - jd[w].left + 1,
            jd[w].zs1 = jd[w].right - jd[w].left + 1, jd[w].zx1 = jd[w].right - jd[w].left + 1;
            jd[w].lx0 = 0, jd[w].rx0 = 0, jd[w].zs0 = 0, jd[w].zx0 = 0;
            bj[w] = 2;
        } else if (aa == 2) {
            swap(jd[w].lx0, jd[w].lx1), swap(jd[w].rx0, jd[w].rx1), swap(jd[w].zs0, jd[w].zs1),
                swap(jd[w].zx0, jd[w].zx1);
            bj[w] = (bj[w] == 3) ? 0 : (bj[w] == 0) ? 3 : (bj[w] == 1) ? 2 : 1;
        }
        return;
    }
    if (bj[w])
        gx(w);
    if (cc <= jd[w * 2].right)
        gj(w * 2);
    else if (bb >= jd[w * 2 + 1].left)
        gj(w * 2 + 1);
    else {
        gj(w * 2);
        gj(w * 2 + 1);
    }
    jd[w].zs1 = jd[w * 2].zs1 + jd[w * 2 + 1].zs1;
    jd[w].lx1 = max(max(jd[w * 2].lx1, jd[w * 2 + 1].lx1), jd[w * 2].rx1 + jd[w * 2 + 1].zx1);
    jd[w].zx1 = (jd[w * 2].zx1 == jd[w * 2].right - jd[w * 2].left + 1) ? jd[w * 2].zx1 + jd[w * 2 + 1].zx1
                                                                        : jd[w * 2].zx1;
    jd[w].rx1 = (jd[w * 2 + 1].rx1 == jd[w * 2 + 1].right - jd[w * 2 + 1].left + 1)
                    ? jd[w * 2 + 1].rx1 + jd[w * 2].rx1
                    : jd[w * 2 + 1].rx1;
    jd[w].zs0 = jd[w * 2].zs0 + jd[w * 2 + 1].zs0;
    jd[w].lx0 = max(max(jd[w * 2].lx0, jd[w * 2 + 1].lx0), jd[w * 2].rx0 + jd[w * 2 + 0].zx0);
    jd[w].zx0 = (jd[w * 2].zx0 == jd[w * 2].right - jd[w * 2].left + 1) ? jd[w * 2].zx0 + jd[w * 2 + 1].zx0
                                                                        : jd[w * 2].zx0;
    jd[w].rx0 = (jd[w * 2 + 1].rx0 == jd[w * 2 + 1].right - jd[w * 2 + 1].left + 1)
                    ? jd[w * 2 + 1].rx0 + jd[w * 2].rx0
                    : jd[w * 2 + 1].rx0;
}

int main() {
    scanf("%lld%lld", &n, &q);
    for (ll i = 1; i <= n; i++) scanf("%lld", &a[i]);
    js(1, 1, n);
    for (ll i = 1; i <= q; i++) {
        scanf("%lld%lld%lld", &aa, &bb, &cc);
        bb++;
        cc++;
        if (aa <= 2)
            gj(1);
        else if (aa == 3)
            printf("%lld\n", czs(1, bb, cc));
        else
            printf("%lld\n", clx(1, bb, cc));
    }
    return 0;
}