20分求助(附hack数据+调试代码）

源码

#include<iostream>
#include<cstdio>
#define int long long
#define ls(p) (p<<1)
#define rs(p) (p<<1)+1
using namespace std;
const int maxn=1e5+5;
int n,m,OP,L,R;
int a[maxn];
struct t{
    int sum,tag1,tag2;
    int lmax[2],rmax[2],midmax[2];
}tree[maxn<<2];
void push_up(int node,int l,int r,int mid){
    tree[node].sum=tree[ls(node)].sum+tree[rs(node)].sum;
    for(int i=0;i<=1;i++){
        tree[node].lmax[i]=tree[ls(node)].lmax[i];
        if(tree[ls(node)].sum==(mid-l+1)*i)
            tree[node].lmax[i]=tree[rs(node)].lmax[i]+mid-l+1;

        tree[node].rmax[i]=tree[rs(node)].rmax[i];
        if(tree[rs(node)].sum==(r-mid)*i)
            tree[node].rmax[i]=tree[ls(node)].rmax[i]+r-mid;

        tree[node].midmax[i]=tree[ls(node)].rmax[i]+tree[rs(node)].lmax[i];
        tree[node].midmax[i]=max(tree[node].midmax[i],tree[ls(node)].midmax[i]);
        tree[node].midmax[i]=max(tree[node].midmax[i],tree[rs(node)].midmax[i]);
    }
    return ;
}
void push_down(int node,int l,int r,int mid){
    if(tree[node].tag1!=-1){
        int k=tree[node].tag1;
        tree[ls(node)].sum=(mid-l+1)*k;
        tree[rs(node)].sum=(r-mid)*k;

        tree[ls(node)].lmax[k]=tree[ls(node)].rmax[k]=tree[ls(node)].midmax[k]=mid-l+1;
        tree[ls(node)].lmax[!k]=tree[ls(node)].rmax[!k]=tree[ls(node)].midmax[!k]=0;

        tree[rs(node)].lmax[k]=tree[rs(node)].rmax[k]=tree[rs(node)].midmax[k]=r-mid;
        tree[rs(node)].lmax[!k]=tree[rs(node)].rmax[!k]=tree[rs(node)].midmax[!k]=0;

        tree[node].tag1=-1;
        tree[ls(node)].tag1=tree[rs(node)].tag1=k;

        tree[node].tag2=tree[ls(node)].tag2=tree[rs(node)].tag2=0;
    }
    if(tree[node].tag2){
        tree[ls(node)].sum=(mid-l+1)-tree[ls(node)].sum;
        tree[rs(node)].sum=(r-mid)-tree[rs(node)].sum;

        if(tree[ls(node)].tag1!=-1)
            tree[ls(node)].tag1^=1;
        else
            tree[ls(node)].tag2^=1;

        if(tree[rs(node)].tag1!=-1)
            tree[rs(node)].tag1^=1;
        else
            tree[rs(node)].tag2^=1;

        tree[node].tag2=0;

        swap(tree[ls(node)].lmax[0],tree[ls(node)].lmax[1]);
        swap(tree[ls(node)].rmax[0],tree[ls(node)].rmax[1]);
        swap(tree[ls(node)].midmax[0],tree[ls(node)].midmax[1]);

        swap(tree[rs(node)].lmax[0],tree[rs(node)].lmax[1]);
        swap(tree[rs(node)].rmax[0],tree[rs(node)].rmax[1]);
        swap(tree[rs(node)].midmax[0],tree[rs(node)].midmax[1]);
    }
    return ;
}
void build(int node,int l,int r){
    if(l==r){
        tree[node].sum=a[l];
        tree[node].tag1=-1;
        tree[node].lmax[0]=tree[node].rmax[0]=tree[node].midmax[0]=!a[l];
        tree[node].lmax[1]=tree[node].rmax[1]=tree[node].midmax[1]=a[l];
        return ;
    }
    int mid=(l+r)>>1;
    build(ls(node),l,mid);
    build(rs(node),mid+1,r);
    push_up(node,l,r,mid);
    tree[node].tag1=-1;
    return ;
}
void update(int node,int l,int r,int aim_L,int aim_R,int op){
    if(l>aim_R||r<aim_L)
        return ;
    if(aim_L<=l&&r<=aim_R){
        if(op<=1){
            tree[node].tag1=op;
            tree[node].sum=(r-l+1)*op;
            tree[node].lmax[op]=tree[node].rmax[op]=tree[node].midmax[op]=r-l+1;
            tree[node].lmax[!op]=tree[node].rmax[!op]=tree[node].midmax[!op]=0;
        }
        else{
            tree[node].tag2^=1;
            tree[node].sum=(r-l+1)-tree[node].sum;
            swap(tree[node].lmax[0],tree[node].lmax[1]);
            swap(tree[node].rmax[0],tree[node].rmax[1]);
            swap(tree[node].midmax[0],tree[node].midmax[1]);
        }
        return ;
    }
    int mid=(l+r)>>1;
    push_down(node,l,r,mid);
    update(ls(node),l,mid,aim_L,aim_R,op);
    update(rs(node),mid+1,r,aim_L,aim_R,op);
    push_up(node,l,r,mid);
    return ;
}
int query1(int node,int l,int r,int aim_L,int aim_R){
    if(l>aim_R||r<aim_L)
        return 0;
//  cout<<node<<' '<<tree[node].sum<<' '<<l<<' '<<r<<endl;
    if(aim_L<=l&&r<=aim_R)
        return tree[node].sum;
    int mid=(l+r)>>1;
    push_down(node,l,r,mid);
    int lsum=query1(ls(node),l,mid,aim_L,aim_R);
    int rsum=query1(rs(node),mid+1,r,aim_L,aim_R);
    return lsum+rsum;
}
t query2(int node,int l,int r,int aim_L,int aim_R){
//  cout<<l<<' '<<r<<endl;
//  cout<<tree[node].lmax[1]<<endl;
    if(aim_L<=l&&r<=aim_R)
        return tree[node];
    int mid=(l+r)>>1;
    push_down(node,l,r,mid);
    if(mid>=aim_R)
        return query2(ls(node),l,mid,aim_L,aim_R);
    if(mid<aim_L)
        return query2(rs(node),mid+1,r,aim_L,aim_R);
    t res;
    t l_res=query2(ls(node),l,mid,aim_L,aim_R);
    t r_res=query2(rs(node),mid+1,r,aim_L,aim_R);
    res.sum=l_res.sum+r_res.sum;
    if(l_res.sum==mid-l+1)
        res.lmax[1]=mid-l+1+r_res.lmax[1];
    else
        res.lmax[1]=l_res.lmax[1];

    if(r_res.sum==r-mid)
        res.rmax[1]=r-mid+l_res.rmax[1];
    else
        res.rmax[1]=r_res.rmax[1];

    res.midmax[1]=l_res.rmax[1]+r_res.lmax[1];
    res.midmax[1]=max(res.midmax[1],l_res.midmax[1]);
    res.midmax[1]=max(res.midmax[1],r_res.midmax[1]);
    return res;
}
signed main(){
    scanf("%lld%lld",&n,&m);
    for(int i=1;i<=n;i++)
        scanf("%lld",&a[i]);
    build(1,1,n);
    while(m--){
//      cout<<tree[14].lmax[1]<<endl;
        scanf("%lld%lld%lld",&OP,&L,&R);
        L++;
        R++;
//      cout<<OP<<' '<<L<<' '<<R<<endl;
        if(OP<=2)
            update(1,1,n,L,R,OP);
        if(OP==3)
            printf("%lld\n",query1(1,1,n,L,R));
        if(OP==4){
            t ans=query2(1,1,n,L,R);
            printf("%lld\n",ans.midmax[1]);
        }
    }
    return 0;
}

hack 数据

4 8

0 0 1 0

3 2 4

2 1 4

4 1 3

1 1 4

2 1 4

4 3 3

（注：数据下标从1开始

#include<iostream>
#include<cstdio>
#define int long long
#define ls(p) (p<<1)
#define rs(p) (p<<1)+1
using namespace std;
const int maxn=1e5+5;
int n,m,OP,L,R;
int a[maxn];
struct t{
    int sum,tag1,tag2;
    int lmax[2],rmax[2],midmax[2];
}tree[maxn<<2];
void push_up(int node,int l,int r,int mid){
    tree[node].sum=tree[ls(node)].sum+tree[rs(node)].sum;
    for(int i=0;i<=1;i++){
        tree[node].lmax[i]=tree[ls(node)].lmax[i];
        if(tree[ls(node)].sum==(mid-l+1)*i)
            tree[node].lmax[i]=tree[rs(node)].lmax[i]+mid-l+1;

        tree[node].rmax[i]=tree[rs(node)].rmax[i];
        if(tree[rs(node)].sum==(r-mid)*i)
            tree[node].rmax[i]=tree[ls(node)].rmax[i]+r-mid;

        tree[node].midmax[i]=tree[ls(node)].rmax[i]+tree[rs(node)].lmax[i];
        tree[node].midmax[i]=max(tree[node].midmax[i],tree[ls(node)].midmax[i]);
        tree[node].midmax[i]=max(tree[node].midmax[i],tree[rs(node)].midmax[i]);
    }
    return ;
}
void push_down(int node,int l,int r,int mid){
    if(tree[node].tag1!=-1){
        int k=tree[node].tag1;
        tree[ls(node)].sum=(mid-l+1)*k;
        tree[rs(node)].sum=(r-mid)*k;

        tree[ls(node)].lmax[k]=tree[ls(node)].rmax[k]=tree[ls(node)].midmax[k]=mid-l+1;
        tree[ls(node)].lmax[!k]=tree[ls(node)].rmax[!k]=tree[ls(node)].midmax[!k]=0;

        tree[rs(node)].lmax[k]=tree[rs(node)].rmax[k]=tree[rs(node)].midmax[k]=r-mid;
        tree[rs(node)].lmax[!k]=tree[rs(node)].rmax[!k]=tree[rs(node)].midmax[!k]=0;

        tree[node].tag1=-1;
        tree[ls(node)].tag1=tree[rs(node)].tag1=k;

        tree[node].tag2=tree[ls(node)].tag2=tree[rs(node)].tag2=0;
    }
    if(tree[node].tag2){
        tree[ls(node)].sum=(mid-l+1)-tree[ls(node)].sum;
        tree[rs(node)].sum=(r-mid)-tree[rs(node)].sum;

        if(tree[ls(node)].tag1!=-1)
            tree[ls(node)].tag1^=1;
        else
            tree[ls(node)].tag2^=1;

        if(tree[rs(node)].tag1!=-1)
            tree[rs(node)].tag1^=1;
        else
            tree[rs(node)].tag2^=1;

        tree[node].tag2=0;

        swap(tree[ls(node)].lmax[0],tree[ls(node)].lmax[1]);
        swap(tree[ls(node)].rmax[0],tree[ls(node)].rmax[1]);
        swap(tree[ls(node)].midmax[0],tree[ls(node)].midmax[1]);

        swap(tree[rs(node)].lmax[0],tree[rs(node)].lmax[1]);
        swap(tree[rs(node)].rmax[0],tree[rs(node)].rmax[1]);
        swap(tree[rs(node)].midmax[0],tree[rs(node)].midmax[1]);
    }
    return ;
}
void build(int node,int l,int r){
    if(l==r){
        tree[node].sum=a[l];
        tree[node].tag1=-1;
        tree[node].lmax[0]=tree[node].rmax[0]=tree[node].midmax[0]=!a[l];
        tree[node].lmax[1]=tree[node].rmax[1]=tree[node].midmax[1]=a[l];
        return ;
    }
    int mid=(l+r)>>1;
    build(ls(node),l,mid);
    build(rs(node),mid+1,r);
    push_up(node,l,r,mid);
    tree[node].tag1=-1;
    return ;
}
void update(int node,int l,int r,int aim_L,int aim_R,int op){
    if(l>aim_R||r<aim_L)
        return ;
    if(aim_L<=l&&r<=aim_R){
        if(op<=1){
            tree[node].tag1=op;
            tree[node].sum=(r-l+1)*op;
            tree[node].lmax[op]=tree[node].rmax[op]=tree[node].midmax[op]=r-l+1;
            tree[node].lmax[!op]=tree[node].rmax[!op]=tree[node].midmax[!op]=0;
        }
        else{
            tree[node].tag2^=1;
            tree[node].sum=(r-l+1)-tree[node].sum;
            swap(tree[node].lmax[0],tree[node].lmax[1]);
            swap(tree[node].rmax[0],tree[node].rmax[1]);
            swap(tree[node].midmax[0],tree[node].midmax[1]);
        }
        return ;
    }
    int mid=(l+r)>>1;
    push_down(node,l,r,mid);
    update(ls(node),l,mid,aim_L,aim_R,op);
    update(rs(node),mid+1,r,aim_L,aim_R,op);
    push_up(node,l,r,mid);
    return ;
}
int query1(int node,int l,int r,int aim_L,int aim_R){
    if(l>aim_R||r<aim_L)
        return 0;
//  cout<<node<<' '<<tree[node].sum<<' '<<l<<' '<<r<<endl;
    if(aim_L<=l&&r<=aim_R)
        return tree[node].sum;
    int mid=(l+r)>>1;
    push_down(node,l,r,mid);
    int lsum=query1(ls(node),l,mid,aim_L,aim_R);
    int rsum=query1(rs(node),mid+1,r,aim_L,aim_R);
    return lsum+rsum;
}
t query2(int node,int l,int r,int aim_L,int aim_R){
//  cout<<l<<' '<<r<<endl;
//  cout<<tree[node].lmax[1]<<endl;
    if(aim_L<=l&&r<=aim_R)
        return tree[node];
    int mid=(l+r)>>1;
    push_down(node,l,r,mid);
    if(mid>=aim_R)
        return query2(ls(node),l,mid,aim_L,aim_R);
    if(mid<aim_L)
        return query2(rs(node),mid+1,r,aim_L,aim_R);
    t res;
    t l_res=query2(ls(node),l,mid,aim_L,aim_R);
    t r_res=query2(rs(node),mid+1,r,aim_L,aim_R);
    res.sum=l_res.sum+r_res.sum;
    if(l_res.sum==mid-l+1)
        res.lmax[1]=mid-l+1+r_res.lmax[1];
    else
        res.lmax[1]=l_res.lmax[1];

    if(r_res.sum==r-mid)
        res.rmax[1]=r-mid+l_res.rmax[1];
    else
        res.rmax[1]=r_res.rmax[1];

    res.midmax[1]=l_res.rmax[1]+r_res.lmax[1];
    res.midmax[1]=max(res.midmax[1],l_res.midmax[1]);
    res.midmax[1]=max(res.midmax[1],r_res.midmax[1]);
    return res;
}
void out(int node,int l,int r){
    cout<<node<<' '<<l<<' '<<r<<endl;
    cout<<tree[node].tag1<<' '<<tree[node].tag2<<' '<<tree[node].sum<<endl;
    int mid=(l+r)>>1;
    if(l<r){
        out(ls(node),l,mid);
        out(rs(node),mid+1,r);
    }
}
signed main(){
    scanf("%lld%lld",&n,&m);
    for(int i=1;i<=n;i++)
        scanf("%lld",&a[i]);
    build(1,1,n);
    while(m--){
        scanf("%lld%lld%lld",&OP,&L,&R);
//      L++;
//      R++;
//      cout<<OP<<' '<<L<<' '<<R<<endl;
        if(OP<=2)
            update(1,1,n,L,R,OP);
        if(OP==3)
            printf("%lld\n",query1(1,1,n,L,R));
        if(OP==4){
            t ans=query2(1,1,n,L,R);
            printf("%lld\n",ans.midmax[1]);
        }
        out(1,1,n);
    }
    return 0;
}