求助&&玄关

Targanzqq @ 2024-05-08 19:58:30

#include<bits/stdc++.h>
#define N 114514
#define int long long
using namespace std;

int n,m,a[N];

struct segtree{
    int tr[5*N];
    int sum[5*N];//维护区间内1的个数 
    int flat0[5*N];//维护区间推平为0
    int flat1[5*N];//维护区间推平为1
    int opo[5*N];//维护区间01反转
    int lxl1[5*N];//维护区间左连续1个数
    int lxr1[5*N];//维护区间内右连续1个数 
    int lxl0[5*N];//维护区间内左连续0个数
    int lxr0[5*N];//维护区间内右连续0个数
    int lres[5*N];//维护每次求答案时范围内左连续1个数 
    int rres[5*N];//维护每次求答案时范围内右连续1个数 
    void push_up(int l,int r,int k){
        sum[k]=sum[2*k]+sum[2*k+1];
        lxl1[k]=lxl1[2*k];
        lxl0[k]=lxl0[2*k];
        lxr1[k]=lxr1[2*k+1];
        lxr0[k]=lxr0[2*k+1];
        if(flat1[2*k])lxl1[k]+=lxl1[2*k+1];
        if(flat0[2*k])lxl0[k]+=lxl0[2*k+1];
        if(flat1[2*k+1])lxr1[k]+=lxr1[2*k];
        if(flat0[2*k+1])lxr0[k]+=lxr0[2*k];
    } 
    void built(int k,int l,int r){
        if(l==r){
            sum[k]=a[l];
            if(sum[k]==1){
                lxl1[k]=1;
                lxr1[k]=1;
            }
            if(sum[k]==0){
                lxl0[k]=1;
                lxr0[k]=1;
            }
            return;
        }
        int mid=(l+r)/2;
        built(2*k,l,mid);
        built(2*k+1,mid+1,r);
        push_up(l,r,k);
    }
    void ft0(int k,int l,int r){
        int mid=(l+r)/2;
        sum[2*k]=0;sum[2*k+1]=0;
        flat0[2*k]=flat0[k];flat0[2*k+1]=flat0[k];flat0[k]=0;
    }
    void ft1(int k,int l,int r){
        int mid=(l+r)/2;
        sum[2*k]=(mid-l+1);sum[2*k+1]=(r-mid);
        flat1[2*k]=flat1[k];flat1[2*k+1]=flat1[k];flat1[k]=0;
    }
    void opp(int k,int l,int r){
        int mid=(l+r)/2;
        opo[2*k]^=opo[k];opo[2*k+1]^=opo[k];opo[k]=0;
        if(opo[2*k])sum[2*k]=(mid-l+1)-sum[2*k];
        if(opo[2*k+1])sum[2*k+1]=(r-mid)-sum[2*k+1];
    }
    void push_down(int l,int r,int k){
        if(opo[k])opp(k,l,r);
        if(flat0[k])ft0(k,l,r);
        if(flat1[k])ft1(k,l,r);
    }
    void modify(int l,int r,int ql,int qr,int k,int op){
        if(ql<=l&&qr>=r){
            if(op==0){
                flat0[k]=1;sum[k]=0;flat1[k]=0;
                lxl1[k]=0;lxr1[k]=0;lxl0[k]=r-l+1;lxr0[k]=r-l+1;
            }
            if(op==1){
                flat1[k]=1;sum[k]=(r-l+1);flat0[k]=0;
                lxl0[k]=0;lxr0[k]=0;lxl1[k]=r-l+1;lxr1[k]=r-l+1;
            }
            if(op==2){
                opo[k]^=1;sum[k]=r-l+1-sum[k];
                swap(lxl0[k],lxl1[k]);swap(lxr0[k],lxr1[k]);
            }
            return;
        }
        push_down(l,r,k);
        int mid=(l+r)/2;
        if(ql<=mid)modify(l,mid,ql,qr,2*k,op);
        if(qr>mid)modify(mid+1,r,ql,qr,2*k+1,op);
        push_up(l,r,k);
    }
    int query(int l,int r,int ql,int qr,int k,int op){
        if(ql<=l&&qr>=r){
            if(op==3){
                return sum[k];
            }
            if(op==4){
                lres[k]=lxl1[k];rres[k]=lxr1[k];
                return max(lxr1[2*k]+lxl1[2*k+1],max(lxl1[k],lxr1[k]));
            }
        }
        push_down(l,r,k);
        int mid=(l+r)/2,res1=0,res2=0;
        if(ql<=mid)res1=query(l,mid,ql,qr,2*k,op);
        if(qr>mid)res2=query(mid+1,r,ql,qr,2*k+1,op);
        //push_up(l,r,k);
        if(op==3)return res1+res2;
        if(op==4){
            if(ql<=mid){
                lres[k]+=lres[2*k];
                if(qr<=mid)rres[k]+=rres[2*k];
            }
            if(qr>mid){
                rres[k]+=rres[2*k+1];
                if(ql>mid)lres[k]+=lres[2*k+1];
            }
            return max(max(res1,res2),rres[2*k]+lres[2*k+1]);
        }
        return 1;
    }
}seg;

signed main(){
    ios::sync_with_stdio(false);
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    seg.built(1,1,n);
    for(int i=1;i<=m;i++){
        int op,l,r;
        cin>>op>>l>>r;
        if(op<=2){
            seg.modify(1,n,l+1,r+1,1,op);
        } 
        else{
            cout<<seg.query(1,n,l+1,r+1,1,op)<<"\n";
        }
    }
}

by IceKylin @ 2024-05-08 20:20:40

@Targanzqq

#include<bits/stdc++.h>
#define N 114514
#define int long long
using namespace std;

int n,m,a[N];

struct segtree{
    int tr[5*N];
    int sum[5*N];//维护区间内1的个数 
    int flat0[5*N];//维护区间推平为0
    int flat1[5*N];//维护区间推平为1
    int opo[5*N];//维护区间01反转
    int lxl1[5*N];//维护区间左连续1个数
    int lxr1[5*N];//维护区间内右连续1个数 
    int lxl0[5*N];//维护区间内左连续0个数
    int lxr0[5*N];//维护区间内右连续0个数
    int lres[5*N];//维护每次求答案时范围内左连续1个数 
    int rres[5*N];//维护每次求答案时范围内右连续1个数 
    void push_up(int l,int r,int k){
        sum[k]=sum[2*k]+sum[2*k+1];
        lxl1[k]=lxl1[2*k];
        lxl0[k]=lxl0[2*k];
        lxr1[k]=lxr1[2*k+1];
        lxr0[k]=lxr0[2*k+1];
        if(flat1[2*k])lxl1[k]+=lxl1[2*k+1];
        if(flat0[2*k])lxl0[k]+=lxl0[2*k+1];
        if(flat1[2*k+1])lxr1[k]+=lxr1[2*k];
        if(flat0[2*k+1])lxr0[k]+=lxr0[2*k];
    } 
    void built(int k,int l,int r){
        if(l==r){
            sum[k]=a[l];
            if(sum[k]==1){
                lxl1[k]=1;
                lxr1[k]=1;
            }
            if(sum[k]==0){
                lxl0[k]=1;
                lxr0[k]=1;
            }
            return;
        }
        int mid=(l+r)/2;
        built(2*k,l,mid);
        built(2*k+1,mid+1,r);
        push_up(l,r,k);
    }
    void ft0(int k,int l,int r){
        int mid=(l+r)/2;
        sum[2*k]=0;opo[2*k]=0;sum[2*k+1]=0;opo[2*k+1]=0;
        flat0[2*k]=flat0[k];flat0[2*k+1]=flat0[k];flat0[k]=0;
        flat1[2*k]=0;flat1[2*k+1]=0;
    }
    void ft1(int k,int l,int r){
        int mid=(l+r)/2;
        sum[2*k]=(mid-l+1);opo[2*k]=0;sum[2*k+1]=(r-mid);opo[2*k+1]=0;
        flat1[2*k]=flat1[k];flat1[2*k+1]=flat1[k];flat1[k]=0;
        flat0[2*k]=0;flat0[2*k+1]=0;
    }
    void opp(int k,int l,int r){
        int mid=(l+r)/2;
        opo[2*k]^=opo[k];opo[2*k+1]^=opo[k];opo[k]=0;
        if(opo[2*k])sum[2*k]=(mid-l+1)-sum[2*k];
        if(opo[2*k+1])sum[2*k+1]=(r-mid)-sum[2*k+1];
    }
    void push_down(int l,int r,int k){
        if(flat0[k])ft0(k,l,r);
        if(flat1[k])ft1(k,l,r);
        if(opo[k])opp(k,l,r);
    }
    void modify(int l,int r,int ql,int qr,int k,int op){
        if(ql<=l&&qr>=r){
            if(op==0){
                flat0[k]=1;sum[k]=0;flat1[k]=0;opo[k]=0;
                lxl1[k]=0;lxr1[k]=0;lxl0[k]=r-l+1;lxr0[k]=r-l+1;
            }
            if(op==1){
                flat1[k]=1;sum[k]=(r-l+1);flat0[k]=0;opo[k]=0;
                lxl0[k]=0;lxr0[k]=0;lxl1[k]=r-l+1;lxr1[k]=r-l+1;
            }
            if(op==2){
                opo[k]^=1;sum[k]=r-l+1-sum[k];
                swap(lxl0[k],lxl1[k]);swap(lxr0[k],lxr1[k]);
            }
            return;
        }
        push_down(l,r,k);
        int mid=(l+r)/2;
        if(ql<=mid)modify(l,mid,ql,qr,2*k,op);
        if(qr>mid)modify(mid+1,r,ql,qr,2*k+1,op);
        push_up(l,r,k);
    }
    int query(int l,int r,int ql,int qr,int k,int op){
        if(ql<=l&&qr>=r){
            if(op==3){
                return sum[k];
            }
            if(op==4){
                lres[k]=lxl1[k];rres[k]=lxr1[k];
                return max(lxr1[2*k]+lxl1[2*k+1],max(lxl1[k],lxr1[k]));
            }
        }
        push_down(l,r,k);
        int mid=(l+r)/2,res1=0,res2=0;
        if(ql<=mid)res1=query(l,mid,ql,qr,2*k,op);
        if(qr>mid)res2=query(mid+1,r,ql,qr,2*k+1,op);
        if(op==3)return res1+res2;
        if(op==4){
            if(ql<=mid){
                lres[k]+=lres[2*k];
                if(qr<=mid)rres[k]+=rres[2*k];
            }
            if(qr>mid){
                rres[k]+=rres[2*k+1];
                if(ql>mid)lres[k]+=lres[2*k+1];
            }
            return max(max(res1,res2),rres[2*k]+lres[2*k+1]);
        }
        return 1;
    }
}seg;

signed main(){
    ios::sync_with_stdio(false);
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    seg.built(1,1,n);
    for(int i=1;i<=m;i++){
        int op,l,r;
        cin>>op>>l>>r;
        if(op<=2){
            seg.modify(1,n,l+1,r+1,1,op);
        } 
        else{
            cout<<seg.query(1,n,l+1,r+1,1,op)<<"\n";
        }
    }
}

pushdown 有问题，帮你改了一下，其他地方没看。

by Targanzqq @ 2024-05-08 20:22:46

@IceKylin 谢谢/bx/bx/bx