求调,看不出哪里有错啊

P2572 [SCOI2010] 序列操作

FiresonZ @ 2022-07-03 19:13:20

QWQ球球了

#include<iostream>
#include<array>
#include<algorithm>
#include<bitset>
#include<cmath>
using namespace std;
using gg=long long;
struct node{
    gg maxl,maxr,mmax,l,r,sum;
}zero;
array<gg,400010> tag,chr;
array<array<gg,400010>,2> num,maxl,maxr,mmax;
array<gg,100010> list;
void pushdown(const gg &p,const gg &l,const gg &r)
{
    gg mid=(l+r)/2;
    if(tag[p]!=2)
    {
        num[tag[p]^1][p*2]=num[tag[p]^1][p*2+1]=0;
        maxl[tag[p]^1][p*2]=maxl[tag[p]^1][p*2+1]=maxr[tag[p]^1][p*2]=maxr[tag[p]^1][p*2+1]=0;
        mmax[tag[p]^1][p*2]=mmax[tag[p]^1][p*2+1]=0;
        mmax[tag[p]][p*2]=maxr[tag[p]][p*2]=maxl[tag[p]][p*2]=mid-l+1;
        mmax[tag[p]][p*2]=maxr[tag[p]][p*2+1]=maxl[tag[p]][p*2+1]=r-mid;
        num[tag[p]][p*2]=mid-l+1;
        num[tag[p]][p*2+1]=r-mid;
        tag[p*2]=tag[p*2+1]=tag[p];
        chr[p*2]=chr[p*2+1]=false;
        tag[p]=2;
    }
    if(chr[p])
    {
        swap(num[0][p*2],num[1][p*2]);
        swap(num[0][p*2+1],num[1][p*2+1]);
        swap(maxl[0][p*2],maxl[1][p*2]),swap(maxl[0][p*2+1],maxl[1][p*2+1]);
        swap(maxr[0][p*2],maxr[1][p*2]),swap(maxr[0][p*2+1],maxr[1][p*2+1]);
        swap(mmax[0][p*2],mmax[1][p*2]),swap(mmax[0][p*2+1],mmax[1][p*2+1]);
        if(tag[p*2]!=2) tag[p*2]^=1;
        else chr[p*2]^=1;
        if(tag[p*2+1]!=2) tag[p*2+1]^=1;
        else chr[p*2+1]^=1;
        chr[p]=false;
    }
    return;
}
void pushup(const gg &p,const gg &l,const gg &r)
{
    gg mid=(l+r)/2;
    for(gg i=0;i<2;i++)
    {
        if(num[i][p*2]==mid-l+1) maxl[i][p]=mid-l+1+maxl[i][p*2+1];
        else maxl[i][p]=maxl[i][p*2];
        if(num[i][p*2+1]==r-mid) maxr[i][p]=r-mid+maxr[i][p*2];
        else maxr[i][p]=maxr[i][p*2+1];
        mmax[i][p]=max({maxl[i][p],maxr[i][p],maxr[i][p*2]+maxl[i][p*2+1]});
    }
    num[0][p]=num[0][p*2]+num[0][p*2+1];
    num[1][p]=num[1][p*2]+num[1][p*2+1];
    return;
}
void build(const gg &l,const gg &r,const gg &p)
{
    tag[p]=2;
    if(l==r)
    {
        mmax[list[l]][p]=maxl[list[l]][p]=maxr[list[l]][p]=1;
        num[list[l]][p]++;
        return;
    }
    gg mid=(l+r)/2;
    build(l,mid,p*2);
    build(mid+1,r,p*2+1);
    pushup(p,l,r);
    return;
}
void update(const gg &l,const gg &r,const gg &nl,const gg &nr,const gg &p,const gg &k)
{
    pushdown(p,nl,nr);
    if(nl>=l&&nr<=r)
    {
        maxl[k^1][p]=maxr[k^1][p]=mmax[k^1][p]=num[k^1][p]=0;
        maxl[k][p]=maxr[k][p]=mmax[k][p]=num[k][p]=nr-nl+1;
        tag[p]=k;
        chr[p]=false;
        return;
    }
    gg mid=(nl+nr)/2;
    if(mid>=l)
    {
        update(l,r,nl,mid,p*2,k);
    }
    if(mid+1<=r)
    {
        update(l,r,mid+1,nr,p*2+1,k);
    }
    pushup(p,nl,nr);
    return;
}
void turn(const gg &l,const gg &r,const gg &nl,const gg &nr,const gg &p)
{
    if(nl>=l&&nr<=r)
    {
        swap(num[1][p],num[0][p]);
        swap(maxl[0][p],maxl[1][p]),swap(maxr[0][p],maxr[1][p]),swap(mmax[0][p],mmax[1][p]);
        if(tag[p]!=2) tag[p]^=1;
        else chr[p]^=1;
        return;
    }
    gg mid=(nl+nr)/2;
    pushdown(p,nl,nr);
    if(mid>=l)
    {
        turn(l,r,nl,mid,p*2);
    }
    if(mid+1<=r)
    {
        turn(l,r,mid+1,nr,p*2+1);
    }
    pushup(p,nl,nr);
    return;
}
gg getone(const gg &l,const gg &r,const gg &nl,const gg &nr,const gg &p)
{
    if(nl>=l&&nr<=r)
    {
        return num[1][p];
    }
    gg mid=(nl+nr)/2,onetp=0;
    pushdown(p,nl,nr);
    if(mid>=l)
    {
        onetp=getone(l,r,nl,mid,p*2);
    }
    if(mid+1<=r)
    {
        onetp+=getone(l,r,mid+1,nr,p*2+1);
    }
    pushup(p,nl,nr);
    return onetp;
}
node getmax(const gg &l,const gg &r,const gg &nl,const gg &nr,const gg &p)
{
    if(nl>=l&&nr<=r)
    {
        return {maxl[1][p],maxr[1][p],mmax[1][p],nl,nr,num[1][p]};
    }
    gg mid=(nl+nr)/2;
    pushdown(p,nl,nr);
    node re=zero;
    if(mid<l) return getmax(l,r,mid+1,nr,p*2+1);
    if(mid>=r) return getmax(l,r,nl,mid,p*2);
    node lson=getmax(l,r,nl,mid,p*2),rson=getmax(l,r,mid+1,nr,p*2+1);
    if(lson.sum==lson.r-lson.l+1) re.maxl=lson.r-lson.l+1+rson.maxl;
    else re.maxl=lson.maxl;
    if(rson.sum==rson.r-rson.l+1) re.maxr=rson.r-rson.l+1+lson.maxr;
    else re.maxr=rson.maxr;
    re.mmax=max({re.maxl,re.maxr,lson.maxr+rson.maxl});
    re.l=lson.l,re.r=rson.r,re.sum=lson.sum+rson.sum;
    pushup(p,nl,nr);
    return re;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    gg n,m,opt,l,r;
    cin>>n>>m;
    for(gg i=1;i<=n;i++)
    {
        cin>>list[i];
    }
    build(1,n,1);
    while(m--)
    {
        cin>>opt>>l>>r;
        l++,r++;
        if(opt==0)
        {
            update(l,r,1,n,1,0);
        }
        else if(opt==1)
        {
            update(l,r,1,n,1,1);
        }
        else if(opt==2)
        {
            turn(l,r,1,n,1);
        }
        else if(opt==3)
        {
            cout<<getone(l,r,1,n,1)<<'\n';
        }
        else
        {
            cout<<getmax(l,r,1,n,1).mmax<<'\n';
        }
    }
    return 0;
}

by FiresonZ @ 2022-07-04 11:42:44

捞一下


|