讨论区 Hack和样例过了 0pts 悬关求助

或者谁帮我找一组 Hack 也行啊。。。

#include<bits/stdc++.h>
using namespace std;

const int N=100005;
int n,m,opt,l,r;

struct SegTree{
    int l,r,sum,maxl0,maxl1,maxr0,maxr1,ans0,ans1,cover;
    bool lazy;
    #define l(x) tree[x].l
    #define r(x) tree[x].r
    #define sum(x) tree[x].sum
    #define maxl0(x) tree[x].maxl0
    #define maxl1(x) tree[x].maxl1
    #define maxr0(x) tree[x].maxr0
    #define maxr1(x) tree[x].maxr1
    #define ans0(x) tree[x].ans0
    #define ans1(x) tree[x].ans1
    #define cover(x) tree[x].cover
    #define lazy(x) tree[x].lazy 
    SegTree(){l=r=sum=maxl0=maxl1=maxr0=maxr1=ans0=ans1=lazy=0;cover=2;}
}tree[N<<3];

void pushdown(int x){
    int l=l(x),r=r(x),mid=l+r>>1;
    if(cover(x)!=2){
        sum(x<<1)=maxl1(x<<1)=maxr1(x<<1)=ans1(x<<1)=(cover(x)?mid-l+1:0);
        sum(x<<1|1)=maxl1(x<<1|1)=maxr1(x<<1|1)=ans1(x<<1|1)=(cover(x)?r-mid:0);
        maxl0(x<<1)=maxr0(x<<1)=ans0(x<<1)=(cover(x)?0:mid-l+1);
        maxl0(x<<1|1)=maxr0(x<<1|1)=ans0(x<<1|1)=(cover(x)?0:r-mid);
        cover(x<<1)=cover(x<<1|1)=cover(x);
        lazy(x<<1)=lazy(x<<1|1)=0;
        cover(x)=2;
    }
    if(!lazy(x))return;
    if(lazy(x<<1)){
        sum(x<<1)=r(x<<1)-l(x<<1)+1-sum(x<<1);
        swap(maxl0(x<<1),maxl1(x<<1));
        swap(maxr0(x<<1),maxr1(x<<1));
        swap(ans0(x<<1),ans1(x<<1));
    }
    if(lazy(x<<1|1)){
        sum(x<<1|1)=r(x<<1|1)-l(x<<1|1)+1-sum(x<<1|1);
        swap(maxl0(x<<1|1),maxl1(x<<1|1));
        swap(maxr0(x<<1|1),maxr1(x<<1|1));
        swap(ans0(x<<1|1),ans1(x<<1|1));
    }
    lazy(x<<1)^=lazy(x);
    lazy(x<<1|1)^=lazy(x);
    lazy(x)=0;
}

void pushup(int x){
    int l=l(x),r=r(x),mid=l+r>>1;
    sum(x)=sum(x<<1)+sum(x<<1|1);
    maxl0(x)=maxl0(x<<1);
    maxl1(x)=maxl1(x<<1);
    if(sum(x<<1)==0)maxl0(x)+=maxl0(x<<1|1);
    else if(sum(x<<1)==mid-l+1)maxl1(x)+=maxl1(x<<1|1);
    maxr0(x)=maxr0(x<<1|1);
    maxr1(x)=maxr1(x<<1|1);
    if(sum(x<<1|1)==0)maxr0(x)+=maxr0(x<<1);
    else if(sum(x<<1|1)==r-mid)maxr1(x)+=maxr1(x<<1);
    ans0(x)=max(max(maxl0(x),maxr0(x)),maxr0(x<<1)+maxl0(x<<1|1));
    ans1(x)=max(max(maxl1(x),maxr1(x)),maxr1(x<<1)+maxl1(x<<1|1));
}

void build(int x,int l,int r){
    if(l==r){
        l(x)=r(x)=l;
        cin>>sum(x);
        if(sum(x)){
            maxl0(x)=maxr0(x)=ans0(x)=0;
            maxl1(x)=maxr1(x)=ans1(x)=1;
        }else{
            maxl0(x)=maxr0(x)=ans0(x)=1;
            maxl1(x)=maxr1(x)=ans1(x)=0;
        }
        return;
    }
    int mid=l+r>>1;
    build(x<<1,l,mid);
    build(x<<1|1,mid+1,r);
    l(x)=l,r(x)=r;
    pushup(x);
}

void COVER(int x,int askl,int askr,bool opt){
    int l=l(x),r=r(x);
    if(askl<=l&&r<=askr){
        if(opt){
            sum(x)=maxl1(x)=maxr1(x)=ans1(x)=r-l+1;
            maxl0(x)=maxr0(x)=ans0(x)=0;
        }else{
            sum(x)=maxl1(x)=maxr1(x)=ans1(x)=0;
            maxl0(x)=maxr0(x)=ans0(x)=r-l+1;
        }
        lazy(x)=0;
        cover(x)=opt;
        return;
    }
    pushdown(x);
    int mid=l+r>>1;
    if(askl<=mid)COVER(x<<1,askl,askr,opt);
    if(askr>mid)COVER(x<<1|1,askl,askr,opt);
    pushup(x);
}

void modify(int x,int askl,int askr){
    int l=l(x),r=r(x);
    int mid=l+r>>1;
    if(askl<=l&&r<=askr){
        lazy(x)^=1;
        if(lazy(x)){
            sum(x)=r-l+1-sum(x);
            swap(maxl0(x),maxl1(x));
            swap(maxr0(x),maxr1(x));
            swap(ans0(x),ans1(x));
        }
        return;
    }
    pushdown(x);
    if(askl<=mid)modify(x<<1,askl,askr);
    if(askr>mid)modify(x<<1|1,askl,askr);
    pushup(x);
}

SegTree query(int x,int askl,int askr){
    int l=l(x),r=r(x);
    if(askl<=l&&r<=askr)return tree[x];
    int mid=l+r>>1;
    pushdown(x);
    if(askr<=mid)return query(x<<1,askl,askr);
    if(askl>mid)return query(x<<1|1,askl,askr);
    SegTree L=query(x<<1,askl,askr),R=query(x<<1|1,askl,askr),ret;
    ret.l=L.l;
    ret.r=R.r;
    ret.sum=L.sum+R.sum;
    ret.ans1=max(max(L.ans1,R.ans1),L.maxr1+R.maxl1);
    ret.maxl1=L.maxl1;
    ret.maxr1=R.maxr1;
    if(L.sum==L.r-L.l+1)ret.maxl1+=R.maxl1;
    if(R.sum==R.r-R.l+1)ret.maxr1+=L.maxr1;
    return ret;
}

int main(){
    cin>>n>>m;
    build(1,1,n);
    while(m--){
        cin>>opt>>l>>r;
        l++,r++;
        if(opt<2)COVER(1,l,r,opt);
        else if(opt==2)modify(1,l,r);
        else if(opt==3)cout<<query(1,l,r).sum<<endl;
        else cout<<query(1,l,r).ans1<<endl;
    }
}