RE求调

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 2e5+10;
int a[maxn << 2];
struct tree{
    int sum;//1个数 
    int lazy = -1; //修改 
    int tag = 0;//反转 
    int pre[2],lst[2],mx[2]; 
}tr[maxn << 2];

void pushup(int rt,int l,int r)
{
    tr[rt].sum = tr[rt * 2].sum + tr[rt * 2 + 1].sum;
    int mid = (l + r) >> 1;
    for(int i = 0;i <= 1;i++)
    {
        tr[rt].pre[i] = tr[rt * 2].pre[i];
        if(tr[rt * 2].sum == (mid - l + 1) && i == 1)
            tr[rt].pre[i] += tr[rt * 2 + 1].pre[i];
        else if(tr[rt * 2].sum == 0 && i == 0)
            tr[rt].pre[i] += tr[rt * 2 + 1].pre[i];

        tr[rt].lst[i] = tr[rt * 2 + 1].lst[i];
        if(tr[rt * 2 + 1].sum == (r - mid) && i == 1)
            tr[rt].lst[i] += tr[rt * 2].lst[i];
        else if(tr[rt * 2 + 1].sum == 0 && i == 0)
            tr[rt].lst[i] += tr[rt * 2].lst[i];

        tr[rt].mx[i] = max(tr[rt * 2].mx[i],tr[rt * 2 + 1].mx[i]);
        tr[rt].mx[i] = max(tr[rt].mx[i],(tr[rt * 2].lst[i] + tr[rt * 2 + 1].pre[i]));
    }
}

void build(int rt,int l,int r)
{
    tr[rt].lazy = -1;
    if(l == r)
    {
        tr[rt].sum = a[l];
        tr[rt].mx[0] = tr[rt].pre[0] = tr[rt].lst[0] = (a[l] == 0);
        tr[rt].mx[1] = tr[rt].pre[1] = tr[rt].lst[1] = (a[l] == 1);
        return;
    }

    int mid = (l + r) >> 1;
    build(rt * 2,l,mid);
    build(rt * 2 + 1,mid + 1,r);
    pushup(rt,l,r);
}

void pushdown(int rt,int l,int r)
{
    int mid = (l + r) >> 1;
    if(tr[rt].lazy != -1)
    {
        tr[rt].tag = 0;
        int val = tr[rt].lazy;
        tr[rt * 2].sum = (mid - l + 1) * val;
        tr[rt * 2 + 1].sum = (r - mid) * val;

        tr[rt * 2].lazy = tr[rt * 2 + 1].lazy = val;
        tr[rt * 2].tag = tr[rt * 2 + 1].tag = 0;

        tr[rt * 2].mx[val]
        = tr[rt * 2].pre[val]
        = tr[rt * 2].lst[val]
        = (mid - l + 1);

        tr[rt * 2 + 1].mx[val]
        = tr[rt * 2 + 1].pre[val]
        = tr[rt * 2 + 1].lst[val]
        = (r - mid);

        tr[rt * 2].mx[val ^ 1]
        = tr[rt * 2].pre[val ^ 1]
        = tr[rt * 2].lst[val ^ 1]
        = 0;

        tr[rt * 2 + 1].mx[val ^ 1]
        = tr[rt * 2 + 1].pre[val ^ 1]
        = tr[rt * 2 + 1].lst[val ^ 1]
        = 0;

        tr[rt].lazy = -1;
    }
    if(tr[rt].tag)
    {
        tr[rt * 2].sum = (mid - l + 1) - tr[rt * 2].sum;
        tr[rt * 2 + 1].sum = (r - mid) - tr[rt * 2 + 1].sum;

        if(tr[rt * 2].lazy != -1) tr[rt * 2].lazy ^= 1;
        else tr[rt * 2].tag ^= 1;

        if(tr[rt * 2 + 1].lazy != -1) tr[rt * 2 + 1].lazy ^= 1;
        else tr[rt * 2 + 1].tag ^= 1;

        swap(tr[rt * 2].lst[0],tr[rt * 2].lst[1]);
        swap(tr[rt * 2].pre[0],tr[rt * 2].pre[1]);
        swap(tr[rt * 2].mx[0],tr[rt * 2].mx[1]);
        swap(tr[rt * 2 + 1].lst[0],tr[rt * 2 + 1].lst[1]);
        swap(tr[rt * 2 + 1].pre[0],tr[rt * 2 + 1].pre[1]);
        swap(tr[rt * 2 + 1].mx[0],tr[rt * 2 + 1].mx[1]);

        tr[rt].tag = 0;
    }
}

void update(int rt,int l,int r,int x,int y,int val)
{
    if(l >= x && y >= r)
    {
        if(val == 1 || val == 0)
        {
            tr[rt].sum = (r - l + 1) * val;
            tr[rt].lazy = val;
            tr[rt].lst[val] = tr[rt].pre[val] = tr[rt].mx[val] = (r - l + 1);
            tr[rt].lst[val ^ 1] = tr[rt].pre[val ^ 1] = tr[rt].mx[val ^ 1] = 0;
        }
        else if(val == 2)
        {
            tr[rt].sum = (r - l + 1) - tr[rt].sum;
            tr[rt].tag ^= 1;
            swap(tr[rt].lst[0],tr[rt].lst[1]);
            swap(tr[rt].pre[0],tr[rt].pre[1]);
            swap(tr[rt].mx[0],tr[rt].mx[1]);
        }
        return;
    }
    pushdown(rt,l,r);
    int mid = (l + r) >> 1;
    if(l <= mid) update(rt * 2,l,mid,x,y,val);
    if(r > mid) update(rt * 2 + 1,mid + 1,r,x,y,val);
    pushup(rt,l,r);
}

int query(int rt,int l,int r,int x,int y)
{
    if(l >= x && y >= r)
    {
        return tr[rt].sum;
    }
    pushdown(rt,l,r);
    int mid = (l + r) >> 1;
    int ans = 0;
    if(l <= mid) ans = query(rt * 2,l,mid,x,y);
    if(r > mid) ans += query(rt * 2 + 1,mid + 1,r,x,y);
    return ans;
}

tree querys(int rt,int l,int r,int x,int y)
{
    if(l >= x && y >= r)
    {
        return tr[rt];
    }
    pushdown(rt,l,r);
    int mid = (l + r) >> 1;
    if(l > mid) return querys(rt * 2 + 1,mid + 1,r,x,y);
    else if(r <= mid) return querys(rt * 2,l,mid,x,y);
    else
    {
        tree res,ll = querys(rt * 2,l,mid,x,y),rr = querys(rt * 2 + 1,mid + 1,r,x,y);
        res.sum = ll.sum + rr.sum;
        for(int i = 0;i <= 1;i++)
        {
            res.pre[i] = ll.pre[i];
            if(i == 1 && ll.sum == (mid - l + 1))
                res.pre[i] += rr.pre[i];
            if(i == 0 && ll.sum == 0)
                res.pre[i] += rr.pre[i];

            res.lst[i] = rr.lst[i];
            if(i == 1 && rr.sum == (r - mid))
                res.lst[i] += ll.lst[i];
            if(i == 0 && rr.sum == 0)
                res.lst[i] += ll.lst[i];

            res.mx[i] = max(ll.mx[i],rr.mx[i]);
            res.mx[i] = max(res.mx[i],ll.lst[i] + rr.pre[i]);
        }
        return res;
    }
}
signed main()
{
    int n,m;
    cin >> n >> m;
    for(int i = 1;i <= n;i++)
    {
        cin >> a[i];
    }
    build(1,1,n);
    for(int i = 1;i <= m;i++)
    {
        int opt;
        cin >> opt;
        int x,y;
        cin >> x >> y;
        {
            if(opt == 3)
            {
                cout << query(1,1,n,x,y) << endl;
            }
            else if(opt == 4)
            {
                cout << querys(1,1,n,x,y).mx[1] << endl;
            }
            else
            {
                update(1,1,n,x,y,opt);
            }
        }
    }
    return 0;
}