10分求助,实在调不动了

P2572 [SCOI2010] 序列操作

tamamocross @ 2023-10-10 18:36:56

#include<iostream>
const int Max=1e5+1,INF=0x3f3f3f3f; 
using namespace std;
struct node{
    int cov;
    bool rev;
    int l,r;
    int l1,r1;
    int l0,r0;
    int sum_1;
    int m_0,m_1;    
}T[4*Max];
bool a[Max];
void push_up(node &a,node b,node c){
    a.sum_1=b.sum_1+c.sum_1;
    a.l0=b.l0==(b.r-b.l+1)?c.l0+b.l0:b.l0;
    a.r0=c.r0==(c.r-c.l+1)?b.r0+c.r0:c.r0;
    a.l1=(b.l1==(b.r-b.l+1))?c.l1+b.l1:b.l1;
    a.r1=(c.r1==(c.r-c.l+1))?b.r1+c.r1:c.r1;
    a.m_0=max(max(b.m_0,c.m_0),b.r0+c.l0);
    a.m_1=max(max(b.m_1,c.m_1),b.r1+c.l1);
}
void push_up(int p){
    push_up(T[p],T[2*p],T[2*p+1]);
}
void Build(int p,int l,int r){
    T[p].l=l;T[p].r=r;T[p].cov=INF;
    if(l==r){
        if(a[l]==1){
            T[p].m_1=1;T[p].l1=1;T[p].r1=1;T[p].sum_1=1;
        }else{
            T[p].m_0=1;T[p].l0=1;T[p].r0=1;
        }       
        return;
    }
    int mid=(l+r)/2;
    Build(2*p,l,mid);Build(2*p+1,mid+1,r);
    push_up(p);
}
void push_down(int p){
    if(T[p].l==T[p].r){
        return;
    }
    int len1=T[2*p].r-T[2*p].l+1,len2=T[2*p+1].r-T[2*p+1].l+1;
    if(T[p].cov!=INF){      
        bool opt=T[p].cov;  
        T[2*p].l0=len1*!opt;T[2*p+1].l0=len2*!opt;
        T[2*p].l1=len1*opt;T[2*p+1].l1=len2*opt;

        T[2*p].m_0=len1*!opt;T[2*p+1].m_0=len2*!opt;
        T[2*p].m_1=len1*opt;T[2*p+1].m_1=len2*opt;

        T[2*p].r0=len1*!opt;T[2*p+1].r0=len2*!opt;      
        T[2*p].r1=len1*opt;T[2*p+1].r1=len2*opt;
        T[2*p].sum_1=len1*opt;T[2*p+1].sum_1=len2*opt;
        T[2*p].rev=0;T[2*p+1].rev=0;
    }if(T[p].rev){
        swap(T[2*p].l0,T[2*p].l1);swap(T[2*p+1].l0,T[2*p+1].l1);
        swap(T[2*p].m_0,T[2*p].m_1);swap(T[2*p+1].m_0,T[2*p+1].m_1);
        swap(T[2*p].r0,T[2*p].r1);swap(T[2*p+1].r0,T[2*p+1].r1);
        T[2*p].sum_1=len1-T[2*p].sum_1;T[2*p+1].sum_1=len2-T[2*p+1].sum_1;
        T[2*p].rev^=1;T[2*p+1].rev^=1;
    }
    T[p].rev=0;
    T[p].cov=INF;
}
void COV(int p,int l,int r,bool val){
    int len=T[p].r-T[p].l+1;
    if(l<=T[p].l&&T[p].r<=r){
        T[p].cov=val;
        T[p].l0=len*!val;
        T[p].l1=len*val;
        T[p].m_0=len*!val;
        T[p].m_1=len*val;
        T[p].r0=len*!val;
        T[p].r1=len*val;
        T[p].sum_1=len*val;
        T[p].rev=0;
        return;
    }
    push_down(p);
    int mid=(T[p].l+T[p].r)/2;
    if(l<=mid){
        COV(2*p,l,r,val);
    }
    if(r>mid){
        COV(2*p+1,l,r,val);
    }
    push_up(p);
}
void REV(int p,int l,int r){
    int len=T[p].r-T[p].l+1;
    bool val=T[p].rev;
    if(l<=T[p].l&&T[p].r<=r){
        swap(T[p].l0,T[p].l1);
        swap(T[p].m_0,T[p].m_1);
        swap(T[p].r0,T[p].r1);
        T[p].sum_1=len-T[p].sum_1;
        T[p].rev^=1;
        return;
    }
    push_down(p);
    int mid=(T[p].l+T[p].r)/2;
    if(l<=mid){
        REV(2*p,l,r);
    }
    if(r>mid){
        REV(2*p+1,l,r);
    }
    push_up(p);
}
node query(int p,int l,int r){
    push_down(p);
    if(l<=T[p].l&&T[p].r<=r){
        return T[p];
    }
    node tmp;
    //cout<<l<<" "<<r<<" "<<T[p].l<<" "<<T[p].r<<" "<<T[p].sum_1<<endl; 
    int mid=(T[p].l+T[p].r)/2;
    if(l>mid){
        tmp=query(2*p+1,l,r);
    }else if(r<=mid){
        tmp=query(2*p,l,r);
    }else{
        push_up(tmp,query(2*p,l,r),query(2*p+1,l,r));   
    }
    push_up(p);

    return tmp;
}
void print(int p){
    cout<<T[p].l<<" "<<T[p].r<<" "<<T[p].l0<<" "<<T[p].r0<<" "<<T[p].l1<<" "<<T[p].r1<<" "<<T[p].m_1<<;
    if(T[p].l==T[p].r){ 
        return;
    }
    print(2*p);
    print(2*p+1);
}
int main(){
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    Build(1,1,n);
    //print(1);cout<<endl;
    for(int i=1;i<=m;i++){
        int opt;cin>>opt;
        int x,y;
        cin>>x>>y;x++;y++;
        if(opt==0||opt==1){
            COV(1,x,y,opt);
        }else if(opt==2){
            REV(1,x,y);
        }else if(opt==3){
            cout<<query(1,x,y).sum_1<<'\n';
        }else{
            cout<<query(1,x,y).m_1<<'\n';
        }
        //print(1);cout<<endl;
    }
} 
/*
10 2
0 0 0 1 1 0 1 0 1 1
1 0 2
3 0 5

/*8 1
0 1 0 1 0 1 0 0
2 1 5
*/

// 0 0 0 1 1 0 1 0 1 1 
// 1 1 1 1 1 0 1 0 1 1 102
// 1 1 1 1 1 0 1 0 1 1 305
// 1 1 0 1 1 0 1 0 1 1 222
// 1 1 0 1 1 0 1 0 1 1 404
// 1 1 0 0 0 0 0 0 1 1 036
// 1 1 0 1 1 1 1 1 1 1 237

by tamamocross @ 2023-10-11 00:25:43

已过,忘下传标记了


|