线段树求调 0pts

#include <bits/stdc++.h>
#define int long long
using namespace std;
inline int read(){
    int now=0,nev=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')nev=-1;c=getchar();}
    while(c>='0'&&c<='9'){now=(now<<1)+(now<<3)+(c&15);c=getchar(); }
    return now*nev;
}

#define ls(x) x * 2
#define rs(x) x * 2 + 1
#define range(x) t[x].r - t[x].l + 1

const int N = 5e5 + 5;
struct Node{
    int l, r;
    int pre0, suf0, pre1, suf1;
    int dat0, dat1;
    int sum, r0, r1, r2;
} t[N << 2];
int a[N];
int n, m;

void push_up(int x){
    t[x].sum = t[ls(x)].sum + t[rs(x)].sum;
    t[x].pre0 = t[ls(x)].pre0;
    if (t[ls(x)].pre0 == range(ls(x)))
        t[x].pre0 = t[ls(x)].pre0 + t[rs(x)].pre0;
    t[x].pre1 = t[ls(x)].pre1;
    if (t[ls(x)].pre1 == range(ls(x)))
        t[x].pre1 = t[ls(x)].pre1 + t[rs(x)].pre1;
    t[x].suf0 = t[rs(x)].suf0;
    if (t[rs(x)].suf0 == range(rs(x)))
        t[x].suf0 = t[ls(x)].suf0 + t[rs(x)].suf0;
    t[x].suf1 = t[rs(x)].suf1;
    if (t[rs(x)].suf1 == range(rs(x)))
        t[x].suf1 = t[ls(x)].suf1 + t[rs(x)].suf1;
    t[x].dat1 = max({t[ls(x)].dat1, t[rs(x)].dat1, t[ls(x)].suf1 + t[rs(x)].pre1});
    t[x].dat0 = max({t[ls(x)].dat0, t[rs(x)].dat0, t[ls(x)].suf0 + t[rs(x)].pre0});
}

void push_down(int x){
    if (t[x].r0){
        t[ls(x)].r0 = t[rs(x)].r0 = 1;
        t[ls(x)].sum = t[rs(x)].sum = 0;
        t[ls(x)].pre0 = t[ls(x)].suf0 = range(ls(x));
        t[ls(x)].suf1 = t[ls(x)].pre1 = 0;
        t[rs(x)].pre0 = t[rs(x)].suf0 = range(rs(x));
        t[rs(x)].suf1 = t[rs(x)].pre1 = 0;
        t[ls(x)].dat0 = range(ls(x));
        t[rs(x)].dat0 = range(rs(x));
        t[ls(x)].dat1 = t[rs(x)].dat1 = 0;
        t[x].r0 = 0;
    }
    if (t[x].r1){
        t[ls(x)].r1 = t[rs(x)].r1 = 1;
        t[ls(x)].sum = range(ls(x));
        t[rs(x)].sum = range(rs(x));
        t[ls(x)].pre1 = t[ls(x)].suf1 = range(ls(x));
        t[ls(x)].suf0 = t[ls(x)].pre0 = 0;
        t[rs(x)].pre1 = t[rs(x)].suf1 = range(rs(x));
        t[rs(x)].suf0 = t[rs(x)].pre0 = 0;
        t[ls(x)].dat1 = range(ls(x));
        t[rs(x)].dat1 = range(rs(x));
        t[ls(x)].dat0 = t[rs(x)].dat0 = 0;
        t[x].r1 = 0;
    }
    if (t[x].r2){
        t[ls(x)].r2 ^= 1, t[rs(x)].r1 ^= 1;
        swap(t[ls(x)].pre0, t[ls(x)].pre1);
        swap(t[ls(x)].suf0, t[ls(x)].suf1);
        swap(t[rs(x)].pre0, t[rs(x)].pre1);
        swap(t[rs(x)].suf0, t[rs(x)].suf1);
        swap(t[ls(x)].dat0, t[ls(x)].dat1);
        swap(t[rs(x)].dat0, t[rs(x)].dat1);
        t[ls(x)].sum = range(ls(x)) - t[ls(x)].sum;
        t[rs(x)].sum = range(rs(x)) - t[rs(x)].sum;
        t[x].r2 = 0;
    }
}

void build(int x, int l, int r){
    t[x].l = l, t[x].r = r;
    if (l == r){
        if (a[l] == 0){
            t[x].suf0 = t[x].pre0 = 1;
            t[x].suf1 = t[x].pre1 = 0;
            t[x].sum = t[x].dat1 = 0;
            t[x].dat0 = 1;
        }
        else{
            t[x].suf1 = t[x].pre1 = 1;
            t[x].suf0 = t[x].pre0 = 0;
            t[x].sum = t[x].dat1 = 1;
            t[x].dat0 = 0;
        }
        return ;
    }
    int mid = (l + r) >> 1;
    build(ls(x), l, mid);
    build(rs(x), mid + 1, r);
    push_up(x);
}

void update0(int x, int l, int r){
    if (l <= t[x].l && t[x].r <= r){
        t[x].sum = 0;
        t[x].r0 = 1, t[x].r1 = 0;
        t[x].pre0 = t[x].suf0 = range(x);
        t[x].suf1 = t[x].pre1 = t[x].dat1 = 0;
        t[x].dat0 = range(x);
        return ;
    }
    push_down(x);
    int mid = (t[x].l + t[x].r) >> 1;
    if (l <= mid) update0(ls(x), l, r);
    if (r > mid) update0(rs(x), l, r);
    push_up(x); 
}

void update1(int x, int l, int r){
    if (l <= t[x].l && t[x].r <= r){
        t[x].sum = range(x);
        t[x].r1 = 1, t[x].r0 = 0;
        t[x].pre0 = t[x].suf0 = 0;
        t[x].pre1 = t[x].suf1 = t[x].dat1 = range(x);
        t[x].dat0 = 0;
        return ;
    }
    push_down(x); 
    int mid = (t[x].l + t[x].r) >> 1;
    if (l <= mid) update1(ls(x), l, r);
    if (r > mid) update1(rs(x), l, r);
    push_up(x);
}

void update2(int x, int l, int r){
    if (l <= t[x].l && t[x].r <= r){
        swap(t[x].suf0, t[x].suf1);
        swap(t[x].pre0, t[x].pre1);
        swap(t[x].dat0, t[x].dat1);
        t[x].r2 ^= 1;
        return ;
    }
    push_down(x); 
    int mid = (t[x].l + t[x].r) >> 1;
    if (l <= mid) update2(ls(x), l, r);
    if (r > mid) update2(rs(x), l, r);
    push_up(x); 
}

int query3(int x, int l, int r){
    if (l <= t[x].l && t[x].r <= r) return t[x].sum;
    push_down(x);
    int mid = (t[x].l + t[x].r) >> 1;
    int val = 0;
    if (l <= mid) val += query3(ls(x), l, r);
    if (r > mid) val += query3(rs(x), l, r);
    return val; 
}

Node query4(int x, int l, int r){
    if (l <= t[x].l && t[x].r <= r) return t[x];
    int mid = (t[x].l + t[x].r) >> 1;
    if (l <= mid && r > mid){
        auto lson = query4(ls(x), l, r);
        auto rson = query4(rs(x), l, r);
        Node ans;
        ans.l = lson.l, ans.r = rson.r;
        ans.pre1 = max(lson.pre1, lson.sum + rson.pre1);
        ans.suf1 = max(rson.suf1, rson.sum + lson.suf1);
        ans.dat1 = max({lson.dat1, rson.dat1, lson.suf1 + rson.pre1});
        ans.pre0 = max(lson.pre0, lson.sum + rson.pre0);
        ans.suf0 = max(rson.suf0, rson.sum + lson.suf0);
        ans.dat0 = max({lson.dat0, rson.dat0, lson.suf0 + rson.pre0});
    }
    else if (l <= mid) return query4(ls(x), l, r);
    else return query4(rs(x), l, r);
} 

signed main()
{
    n = read(), m = read();
    for (int i = 1; i <= n; i ++) a[i] = read();
    build(1, 1, n);
    while (m --){
        int op = read(), l = read() + 1, r = read() + 1;
        if (op == 0) update0(1, l, r);
        if (op == 1) update1(1, l, r);
        if (op == 2) update2(1, l, r);
        if (op == 3)
            cout << query3(1, l, r) << "\n";
        if (op == 4){
            auto tmp = query4(1, l, r);
            cout << tmp.dat1 << "\n";
        }
    } 
    return 0;
}

rt，实在不知道哪里寄了。