新人求助,序列操作那题,本地没有AC提交WA

P2572 [SCOI2010] 序列操作

lndjy @ 2020-04-04 20:16:25

样例过了提交爆零WA:

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
struct node
{
    int amax,lmax,rmax;
    int len;
};
int inline read()
{
    int ans=0,f=1;
    char ch=getchar();
    while(!isdigit(ch))
    {
        if(ch=='-')
        f=-1;
        ch=getchar();
    }
    while(isdigit(ch))
    {
        ans=ans*10+ch-'0';
        ch=getchar();
    }
    return ans*f;
}
struct tree
{
    int l,r;
    int len;
    int sum,lmax[2],rmax[2],amax[2];
    int lazy;
}t[400005];
int n,m,a[100005];
void pushup(int k)
{
    t[k].sum=t[k*2].sum+t[k*2+1].sum;
    for(int i=0;i<=1;i++)
    {
        t[k].lmax[i]=(t[k*2].lmax[i]==t[k*2].len?t[k*2].lmax[i]+t[k*2+1].lmax[i]:t[k*2].lmax[i]);
        t[k].rmax[i]=(t[k*2+1].rmax[i]==t[k*2+1].len?t[k*2+1].rmax[i]+t[k*2].rmax[i]:t[k*2+1].rmax[i]);
        t[k].amax[i]=max(t[k*2].amax[i],max(t[k*2+1].amax[i],t[k*2].rmax[i]+t[k*2+1].lmax[i]));
    }
} 
void pushdown(int k)
{
    if(t[k].lazy==0)
    {
        t[k*2].sum=t[k*2].lmax[1]=t[k*2].rmax[1]=t[k*2].amax[1]=t[k*2].lazy=0;
        t[k*2+1].sum=t[k*2+1].lmax[1]=t[k*2+1].rmax[1]=t[k*2+1].amax[1]=t[k*2+1].lazy=0;
        t[k*2].lmax[0]=t[k*2].rmax[0]=t[k*2].amax[0]=t[k*2].len;
        t[k*2+1].lmax[0]=t[k*2+1].rmax[0]=t[k*2+1].amax[0]=t[k*2+1].len;
    }
    if(t[k].lazy==1)
    {
        t[k*2].sum=t[k*2].amax[1]=t[k*2].lmax[1]=t[k*2].rmax[1]=t[k*2].len;
        t[k*2+1].sum=t[k*2+1].amax[1]=t[k*2+1].lmax[1]=t[k*2+1].rmax[1]=t[k*2+1].len;
        t[k*2].lazy=t[k*2+1].lazy=1;
        t[k*2].lmax[0]=t[k*2].rmax[0]=t[k*2].amax[0]=0;
        t[k*2+1].lmax[0]=t[k*2+1].rmax[0]=t[k*2+1].amax[0]=0;
    }
    if(t[k].lazy==2)
    {
        t[k*2].sum=t[k*2].len-t[k*2].sum;
        t[k*2+1].sum=t[k*2+1].len-t[k*2+1].sum;
        t[k*2].lazy=t[k*2+1].lazy=2;
        swap(t[k*2].lmax[0],t[k*2].lmax[1]);swap(t[k*2].rmax[0],t[k*2].rmax[1]);swap(t[k*2].amax[0],t[k*2].amax[1]);
        swap(t[k*2+1].lmax[0],t[k*2+1].lmax[1]);swap(t[k*2+1].rmax[0],t[k*2+1].rmax[1]);swap(t[k*2+1].amax[0],t[k*2+1].amax[1]);
    }
    t[k].lazy=-1;
}
void build(int l,int r,int k)
{
    t[k].l=l;t[k].r=r;t[k].len=r-l+1;
    t[k].lazy=-1;
    if(l==r)
    {
        t[k].sum=a[l];
        t[k].lmax[a[l]]=t[k].rmax[a[l]]=t[k].amax[a[l]]=1;
        return;
    }
    int mid=(l+r)/2;
    build(l,mid,k*2);
    build(mid+1,r,k*2+1);
    pushup(k);
}
void change(int l,int r,int k,int v)
{
    if(l<=t[k].l&&t[k].r<=r)
    {
        if(v==0) t[k].sum=0;
        else t[k].sum=t[k].len;
        t[k].lazy=v;
        t[k].lmax[v]=t[k].rmax[v]=t[k].amax[v]=t[k].len;
        t[k].lmax[!v]=t[k].rmax[!v]=t[k].amax[!v]=0;
        return;
    }
    pushdown(k);
    if(t[k*2].r>=l)
    change(l,r,k*2,v);
    if(t[k*2+1].l<=r)
    change(l,r,k*2+1,v);
    pushup(k);
}
void no(int l,int r,int k)
{
    if(l<=t[k].l&&t[k].r<=r)
    {
        t[k].sum=t[k].len-t[k].sum;
        swap(t[k].lmax[0],t[k].lmax[1]);swap(t[k].rmax[0],t[k].rmax[1]);swap(t[k].amax[0],t[k].amax[1]);
        if(t[k].lazy==2) t[k].lazy=-1;
        else if(t[k].lazy==-1) t[k].lazy=2;
        else if(t[k].lazy==1) t[k].lazy=0;
        else t[k].lazy=1;
        return;
    }
    pushdown(k);
    if(t[k*2].r>=l)
    no(l,r,k*2);
    if(t[k*2+1].l<=r)
    no(l,r,k*2+1);
    pushup(k);
}
int ask(int l,int r,int k)
{
    if(l<=t[k].l&&t[k].r<=r)
    return t[k].sum;
    pushdown(k);
    int ans=0;
    if(t[k*2].r>=l)
    ans+=ask(l,r,k*2);
    if(t[k*2+1].l<=r)
    ans+=ask(l,r,k*2+1);
    return ans;
}
node askmax(int l,int r,int k)
{
    pushdown(k);
    if(l==t[k].l&&r==t[k].r)
    return (node){t[k].amax[1],t[k].lmax[1],t[k].rmax[1],t[k].len};
    if(t[k*2].r>=r) return askmax(l,r,k*2);
    if(t[k*2+1].l<=l) return askmax(l,r,k*2+1);
    node ans=(node){0,0,0,0};
    node a=askmax(l,t[k*2].r,k*2),b=askmax(t[k*2+1].l,r,k*2+1);
    if(a.lmax==a.len) ans.lmax=a.lmax+b.lmax;
    else ans.lmax=a.lmax;
    if(b.rmax==b.len) ans.rmax=a.rmax+b.rmax;
    else ans.rmax=b.rmax;
    ans.len=a.len+b.len;
    ans.amax=max(a.amax,max(b.amax,a.rmax+b.lmax));
    return ans;
}
int main()
{
    n=read();m=read();
    for(int i=1;i<=n;i++)
    a[i]=read();
    build(1,n,1);
    for(int i=1;i<=m;i++)
    {
        int op=read(),l=read()+1,r=read()+1;
        if(op<=1) change(l,r,1,op);
        if(op==2) no(l,r,1);
        if(op==3) cout<<ask(l,r,1)<<'\n';
        if(op==4) cout<<askmax(l,r,1).amax<<'\n';
     } 
    return 0;
}

by Hexarhy @ 2020-04-04 20:21:00

这么长的代码两个注释都没有怎么看差评


by lndjy @ 2020-04-04 20:21:45

1.在这个蒟蒻都切Ynoi的时代,我确实是新人

2.我确实WA爆零了


by HoshiuZ @ 2020-04-04 20:31:54

@水题淹死的鱼 父节点为lazy值为2时,标记下传时其子节点的标记情况也要分类讨论吧qwq


by HoshiuZ @ 2020-04-04 20:32:51

@水题淹死的鱼 你和我当时思路差不多,都是把标记放在一起的qwq

#include<bits/stdc++.h>
#define N 100010

using namespace std;

int n,m,op,l,r,tot=0;
struct node{
    int l,r,maxn1,lmaxn1,rmaxn1,maxn0,lmaxn0,rmaxn0,lazy,sum;
    #define l(x) tree[x].l
    #define r(x) tree[x].r
    #define m1(x) tree[x].maxn1
    #define lm1(x) tree[x].lmaxn1
    #define rm1(x) tree[x].rmaxn1
    #define m0(x) tree[x].maxn0
    #define lm0(x) tree[x].lmaxn0
    #define rm0(x) tree[x].rmaxn0
    #define lazy(x) tree[x].lazy
    #define s(x) tree[x].sum
    #define ls p<<1
    #define rs p<<1|1
}tree[N<<2];

void push_up(int p) {
    s(p)=s(ls)+s(rs);
    m1(p)=max(rm1(ls)+lm1(rs),max(m1(ls),m1(rs)));
    m0(p)=max(rm0(ls)+lm0(rs),max(m0(ls),m0(rs)));
    if(lm1(ls)==r(ls)-l(ls)+1) lm1(p)=lm1(ls)+lm1(rs);
    else lm1(p)=lm1(ls);
    if(rm1(rs)==r(rs)-l(rs)+1) rm1(p)=rm1(rs)+rm1(ls);
    else rm1(p)=rm1(rs);
    if(lm0(ls)==r(ls)-l(ls)+1) lm0(p)=lm0(ls)+lm0(rs);
    else lm0(p)=lm0(ls);
    if(rm0(rs)==r(rs)-l(rs)+1) rm0(p)=rm0(rs)+rm0(ls);
    else rm0(p)=rm0(rs);
}

void build(int p,int l,int r) {
    l(p)=l,r(p)=r;
    if(l==r) {
        scanf("%d",&s(p));
        lm1(p)=rm1(p)=m1(p)=s(p);
        lm0(p)=rm0(p)=m0(p)=s(p)^1;
        return ;
    }
    int mid=l+r>>1;
    build(ls,l,mid);
    build(rs,mid+1,r);
    push_up(p);
}

void spread(int p) {
    if(!lazy(p)) return ;
    if(lazy(p)==1) {
        s(ls)=s(rs)=0;
        m1(ls)=lm1(ls)=rm1(ls)=0;
        m0(ls)=lm0(ls)=rm0(ls)=r(ls)-l(ls)+1;
        m1(rs)=lm1(rs)=rm1(rs)=0;
        m0(rs)=lm0(rs)=rm0(rs)=r(rs)-l(rs)+1;
        lazy(ls)=1,lazy(rs)=1;
        lazy(p)=0;
    }
    if(lazy(p)==2) {
        s(ls)=r(ls)-l(ls)+1;
        s(rs)=r(rs)-l(rs)+1;
        m1(ls)=lm1(ls)=rm1(ls)=r(ls)-l(ls)+1;
        m0(ls)=lm0(ls)=rm0(ls)=0;
        m1(rs)=lm1(rs)=rm1(rs)=r(rs)-l(rs)+1;
        m0(rs)=lm0(rs)=rm0(rs)=0;
        lazy(ls)=2,lazy(rs)=2;
        lazy(p)=0;
    }
    if(lazy(p)==3) {
        s(ls)=r(ls)-l(ls)+1-s(ls);
        s(rs)=r(rs)-l(rs)+1-s(rs);
        swap(m1(ls),m0(ls)),swap(m1(rs),m0(rs));
        swap(lm1(ls),lm0(ls)),swap(lm1(rs),lm0(rs));
        swap(rm1(ls),rm0(ls)),swap(rm1(rs),rm0(rs));
        if(!lazy(ls)) lazy(ls)=3;
        else if(lazy(ls)==1) lazy(ls)=2;
        else if(lazy(ls)==2) lazy(ls)=1;
        else lazy(ls)=0;
        if(!lazy(rs)) lazy(rs)=3;
        else if(lazy(rs)==1) lazy(rs)=2;
        else if(lazy(rs)==2) lazy(rs)=1;
        else lazy(rs)=0;
        lazy(p)=0;
    }
}

void change(int p,int l,int r,int x) {
    if(l(p)>r||r(p)<l) return ;
    spread(p);
    if(l(p)>=l&&r(p)<=r) {
        if(!x) {
            s(p)=0;
            m1(p)=lm1(p)=rm1(p)=0;
            m0(p)=lm0(p)=rm0(p)=r(p)-l(p)+1;
            lazy(p)=1;
            return ;
        }
        else if(x==1) {
            s(p)=r(p)-l(p)+1;
            m1(p)=lm1(p)=rm1(p)=r(p)-l(p)+1;
            m0(p)=lm0(p)=rm0(p)=0;
            lazy(p)=2;
            return ;
        }
        else {
            s(p)=r(p)-l(p)+1-s(p);
            swap(m1(p),m0(p));
            swap(lm1(p),lm0(p));
            swap(rm1(p),rm0(p));
            lazy(p)=3;
            return ;
        }
    }
    change(ls,l,r,x);
    change(rs,l,r,x);
    push_up(p);
}

int ask(int p,int l,int r,int op) {
    if(op==3) {
        if(l(p)>r||r(p)<l) return 0;
        if(l(p)>=l&&r(p)<=r) {
            return s(p);
        }
        spread(p);
        return ask(ls,l,r,op)+ask(rs,l,r,op);
    }
    else {
        if(l(p)>r||r(p)<l) return 0;
        if(l(p)>=l&&r(p)<=r) return m1(p);
        spread(p);
        return max(max(ask(ls,l,r,op),ask(rs,l,r,op)),min(rm1(ls),r(ls)-l+1)+min(lm1(rs),r-l(rs)+1));
    }
}

int main() {
    scanf("%d%d",&n,&m);

    build(1,1,n);
    for(int i=1;i<=m;i++) {
        scanf("%d%d%d",&op,&l,&r);
        l++,r++;
        if(op<=2) change(1,l,r,op);
        else printf("%d\n",ask(1,l,r,op));
    }

    return 0;
}

by lndjy @ 2020-04-04 20:33:20

@Yuzuriha_Inori 谢谢大佬,我sb了


by JRzyh @ 2020-04-06 15:18:19

本地没有AC

IEE


上一页 |