求助,只过了#11和样例

P2572 [SCOI2010] 序列操作

bktchizhi_fzh @ 2022-11-22 19:37:03

感觉讨论区提醒的也注意了呀

#include<iostream>
#include<cstring>
#include<cstdio>
#define N 100010
#define ls(p) p<<1
#define rs(p) p<<1|1
using namespace std;
int a[N],n,m,op,l,r;
struct Tree{
    int qufan,fugai;
    int sum;
    int lmax1,rmax1,maxn1;
    int lmax0,rmax0,maxn0;
    Tree(){
        fugai=-1;
    }
}tr[4*N];
void push_up(int p,int l,int r){
    int mid=(l+r)>>1;
    tr[p].sum=tr[ls(p)].sum+tr[rs(p)].sum;
    tr[p].lmax1=tr[ls(p)].lmax1==mid-l+1?tr[ls(p)].lmax1+tr[rs(p)].lmax1:tr[ls(p)].lmax1;
    tr[p].rmax1=tr[rs(p)].rmax1==r-mid?tr[rs(p)].rmax1+tr[ls(p)].rmax1:tr[rs(p)].rmax1;
    tr[p].maxn1=max(max(tr[ls(p)].maxn1,tr[rs(p)].maxn1),tr[ls(p)].rmax1+tr[rs(p)].lmax1);
    tr[p].lmax0=tr[ls(p)].lmax0==mid-l+1?tr[ls(p)].lmax0+tr[rs(p)].lmax0:tr[ls(p)].lmax0;
    tr[p].rmax0=tr[rs(p)].rmax0==r-mid?tr[rs(p)].rmax0+tr[ls(p)].rmax0:tr[rs(p)].rmax0;
    tr[p].maxn0=max(max(tr[ls(p)].maxn0,tr[rs(p)].maxn0),tr[ls(p)].rmax0+tr[rs(p)].lmax0);
} 
void push_down(int p,int l,int r){
    int mid=(l+r)>>1;
    if(tr[p].fugai!=-1){
        if(tr[p].fugai==1){
            tr[ls(p)].fugai=1;
            tr[rs(p)].fugai=1;
            tr[ls(p)].qufan=0;
            tr[rs(p)].qufan=0;
            tr[ls(p)].sum=mid-l+1;
            tr[rs(p)].sum=r-mid;
            tr[ls(p)].lmax1=tr[ls(p)].rmax1=tr[ls(p)].maxn1=mid-l+1;
            tr[ls(p)].lmax0=tr[ls(p)].rmax0=tr[ls(p)].maxn0=0;
            tr[rs(p)].lmax1=tr[rs(p)].rmax1=tr[rs(p)].maxn1=r-mid;
            tr[rs(p)].lmax0=tr[rs(p)].rmax0=tr[rs(p)].maxn0=0;
        } else {
            tr[ls(p)].fugai=0;
            tr[rs(p)].fugai=0;
            tr[ls(p)].qufan=0;
            tr[rs(p)].qufan=0;
            tr[ls(p)].sum=0;
            tr[rs(p)].sum=0;
            tr[ls(p)].lmax1=tr[ls(p)].rmax1=tr[ls(p)].maxn1=0;
            tr[ls(p)].lmax0=tr[ls(p)].rmax0=tr[ls(p)].maxn0=mid-l+1;
            tr[rs(p)].lmax1=tr[rs(p)].rmax1=tr[rs(p)].maxn1=0;
            tr[rs(p)].lmax0=tr[rs(p)].rmax0=tr[rs(p)].maxn0=r-mid;
        }
        tr[p].fugai=-1;
    }
    if(tr[p].qufan){
        tr[ls(p)].qufan=tr[p].qufan;
        int l0=tr[ls(p)].lmax0,r0=tr[ls(p)].rmax0,m0=tr[ls(p)].maxn0;
        int l1=tr[ls(p)].lmax1,r1=tr[ls(p)].rmax1,m1=tr[ls(p)].maxn1;
        int sum1=tr[ls(p)].sum;
        tr[ls(p)].sum=mid-l+1-sum1;
        tr[ls(p)].maxn1=m0,tr[ls(p)].lmax1=l0,tr[ls(p)].rmax1=r0;
        tr[ls(p)].maxn0=m1,tr[ls(p)].lmax0=l1,tr[ls(p)].rmax0=r1;
        tr[rs(p)].qufan=tr[p].qufan;
        l0=tr[rs(p)].lmax0,r0=tr[rs(p)].rmax0,m0=tr[rs(p)].maxn0;
        l1=tr[rs(p)].lmax1,r1=tr[rs(p)].rmax1,m1=tr[rs(p)].maxn1;
        sum1=tr[rs(p)].sum;
        tr[rs(p)].sum=r-mid-sum1;
        tr[rs(p)].maxn1=m0,tr[rs(p)].lmax1=l0,tr[rs(p)].rmax1=r0;
        tr[rs(p)].maxn0=m1,tr[rs(p)].lmax0=l1,tr[rs(p)].rmax0=r1;
        tr[p].qufan^=1;
    }
}
void build(int p,int l,int r){
    if(l==r){
        tr[p].fugai=-1;
        tr[p].qufan=0;
        tr[p].lmax1=tr[p].rmax1=tr[p].maxn1=tr[p].sum=a[l];
        tr[p].lmax0=tr[p].rmax0=tr[p].maxn0=a[l]^1;
        return;
    }
    int mid=(l+r)>>1;
    build(ls(p),l,mid);
    build(rs(p),mid+1,r);
    push_up(p,l,r);
}
void Cover0(int p,int l,int r,int x,int y){
    if(x<=l&&r<=y){
        tr[p].fugai=0;
        tr[p].qufan=0;
        tr[p].sum=0;
        tr[p].lmax0=tr[p].rmax0=tr[p].maxn0=r-l+1;
        tr[p].lmax1=tr[p].rmax1=tr[p].maxn1=0;
        return;
    }
    int mid=(l+r)>>1;
    push_down(p,l,r);
    if(mid>=x)Cover0(ls(p),l,mid,x,y);
    if(mid<y)Cover0(rs(p),mid+1,r,x,y);
    push_up(p,l,r);
}
void Cover1(int p,int l,int r,int x,int y){
    if(x<=l&&r<=y){
        tr[p].fugai=1;
        tr[p].qufan=0;
        tr[p].sum=r-l+1;
        tr[p].lmax0=tr[p].rmax0=tr[p].maxn0=0;
        tr[p].lmax1=tr[p].rmax1=tr[p].maxn1=r-l+1;
        return;
    }
    int mid=(l+r)>>1;
    push_down(p,l,r);
    if(mid>=x)Cover1(ls(p),l,mid,x,y);
    if(mid<y)Cover1(rs(p),mid+1,r,x,y);
    push_up(p,l,r);
}
void update(int p,int l,int r,int x,int y){
    if(x<=l&&r<=y){
        tr[p].qufan^=1;
        int m0=tr[p].maxn0,l0=tr[p].lmax0,r0=tr[p].rmax0;
        int m1=tr[p].maxn1,l1=tr[p].lmax1,r1=tr[p].rmax1;
        int sum1=tr[p].sum;
        tr[p].sum=r-l+1-sum1;
        tr[p].maxn1=m0,tr[p].lmax1=l0,tr[p].rmax1=r0;
        tr[p].maxn0=m1,tr[p].lmax0=l1,tr[p].rmax0=r1;
        return;
    }
    int mid=(l+r)>>1;
    push_down(p,l,r);
    if(mid>=x)update(ls(p),l,mid,x,y);
    if(mid<y)update(rs(p),mid+1,r,x,y);
    push_up(p,l,r);
}
int Sum(int p,int l,int r,int x,int y){
    if(x<=l&&r<=y)return tr[p].sum;
    int res=0,mid=(l+r)>>1;
    push_down(p,l,r);
    if(mid>=x)res+=Sum(ls(p),l,mid,x,y);
    if(mid<y)res+=Sum(rs(p),mid+1,r,x,y);
    return res;
}
int Ctn1(int p,int l,int r,int x,int y){
    if(x<=l&&r<=y)return tr[p].maxn1;
    int mid=(l+r)>>1,resl=0,resr=0,res=0;
    push_down(p,l,r);
    if(mid>=x){
        resl=Ctn1(ls(p),l,mid,x,y);
        if(tr[ls(p)].rmax1>mid-x+1)res+=mid-x+1;
        else res+=tr[ls(p)].lmax1;
    }
    if(mid<y){
        resr=Ctn1(rs(p),mid+1,r,x,y);
        if(tr[rs(p)].lmax1>y-mid)res+=y-mid;
        else res+=tr[rs(p)].lmax1;
    }
    return max(max(resl,resr),res);
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    build(1,1,n);
    while(m--){
        scanf("%d%d%d",&op,&l,&r);
        l++;r++;
        if(op==0)Cover0(1,1,n,l,r);
        if(op==1)Cover1(1,1,n,l,r);
        if(op==2)update(1,1,n,l,r);
        if(op==3)printf("%d\n",Sum(1,1,n,l,r));
        if(op==4)printf("%d\n",Ctn1(1,1,n,l,r));
    }
    return 0;
} 

by bktchizhi_fzh @ 2022-11-23 20:09:26

过了,此贴完结


|