80分求助

WA 1,3

#include<bits/stdc++.h>
#define ls(k) k << 1
#define rs(k) k << 1 | 1
using namespace std;

const int MAX_N = 100000 + 5;
int a[MAX_N], sum[MAX_N * 4], tag[MAX_N * 4];
int pre0[MAX_N * 4], pre1[MAX_N * 4];
int nxt0[MAX_N * 4], nxt1[MAX_N * 4];
int max0[MAX_N * 4], max1[MAX_N * 4];

void push_up(int k, int l, int r)
{
    int m = (l + r) >> 1;
    sum[k] = sum[ls(k)] + sum[rs(k)];
    pre1[k] = pre1[ls(k)] + (pre1[ls(k)] == m - l + 1 ? pre1[rs(k)] : 0);
    pre0[k] = pre0[ls(k)] + (pre0[ls(k)] == m - l + 1 ? pre0[rs(k)] : 0);
    nxt1[k] = nxt1[rs(k)] + (nxt1[rs(k)] == r - m ? nxt1[ls(k)] : 0);
    nxt0[k] = nxt0[rs(k)] + (nxt0[rs(k)] == r - m ? nxt0[ls(k)] : 0);
    max1[k] = max(max(max1[ls(k)], max1[rs(k)]), nxt1[ls(k)] + pre1[rs(k)]);
    max0[k] = max(max(max0[ls(k)], max0[rs(k)]), nxt0[ls(k)] + pre0[rs(k)]);
}

void build(int k, int l, int r)
{
    if(l == r) {
        sum[k] = a[l];
        if(a[l] == 1) {
            max1[k] = pre1[k] = nxt1[k] = 1;
            max0[k] = pre0[k] = nxt0[k] = 0;
        } else {
            max1[k] = pre1[k] = nxt1[k] = 0;
            max0[k] = pre0[k] = nxt0[k] = 1;
        }
        return;
    }
    int m = (l + r) >> 1;
    build(ls(k), l, m);
    build(rs(k), m + 1, r);
    push_up(k, l, r);
}

void update(int k, int l, int r, int v)
{
    if(v == 1) {
        sum[k] = 0;
        max0[k] = pre0[k] = nxt0[k] = r - l + 1;
        max1[k] = pre1[k] = nxt1[k] = 0;
        tag[k] = 1;
    } else if(v == 2) {
        sum[k] = r - l + 1;
        max0[k] = pre0[k] = nxt0[k] = 0;
        max1[k] = pre1[k] = nxt1[k] = r - l + 1;
        tag[k] = 2;
    } else if(v == 3) {
        sum[k] = r - l + 1 - sum[k];
        swap(pre1[k], pre0[k]);
        swap(nxt1[k], nxt0[k]);
        swap(max1[k], max0[k]);
        tag[k] = 3 - tag[k];
    }
}

void push_down(int k, int l, int r)
{
    if(tag[k] == 0)
        return;
    int m = (l + r) >> 1;
    update(ls(k), l, m, tag[k]);
    update(rs(k), m + 1, r, tag[k]);
    tag[k] = 0;
}

void modify(int k, int l, int r, int x, int y, int v)
{
    if(l >= x && r <= y) {
        update(k, l, r, v);
        return;
    }
    push_down(k, l, r);
    int m = (l + r) >> 1;
    if(x <= m)
        modify(ls(k), l, m, x, y, v);
    if(m + 1 <= y)
        modify(rs(k), m + 1, r, x, y, v);
    push_up(k, l, r);
}

int query(int k, int l, int r, int x, int y)
{
    if(l >= x && r <= y)
        return sum[k];
    push_down(k, l, r);
    int m = (l + r) >> 1;
    int res = 0;
    if(x <= m)
        res += query(ls(k), l, m, x, y);
    if(m + 1 <= y)
        res += query(rs(k), m + 1, r, x, y);
    return res;
}

int query1(int k, int l, int r, int x, int y)
{
    if(l >= x && r <= y)
        return max1[k];
    push_down(k, l, r);
    int m = (l + r) >> 1;
    int res = 0, t = 0;
    if(x <= m) {
        res = max(res, query1(ls(k), l, m, x, y));
        t += min(nxt1[ls(k)], m - x + 1);
    }
    if(m + 1 <= y) {
        res = max(res, query1(rs(k), m + 1, r, x, y));
        t += min(pre1[rs(k)], y - m);
    }
    return max(res, t);
}

int main()
{
    int n, m;
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i++)
        scanf("%d", &a[i]);
    build(1, 1, n);
    while(m--) {
        int opt, l, r;
        scanf("%d%d%d", &opt, &l, &r);
        l++, r++;
        if(opt <= 2) {
           modify(1, 1, n, l, r, opt + 1);
        } else if(opt == 3) {
            printf("%d\n", query(1, 1, n, l, r));
        } else {
            printf("%d\n", query1(1, 1, n, l, r));
        }
    }
    return 0;
}