新人求助,序列操作那题,本地没有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 听取MLE声一片 @ 2020-04-04 20:16:37

前排


by Wenoide @ 2020-04-04 20:17:19

这种题还是不要问了吧……应该不会有人耐心看的


by lndjy @ 2020-04-04 20:17:19

@听取mc声一片 求助帖你抢个毛线前排


by Spasmodic @ 2020-04-04 20:17:42

QNDXR


by Eon_Sky @ 2020-04-04 20:17:52

QNDXR


by UnyieldingTrilobite @ 2020-04-04 20:18:54

btd危


by IntrepidStrayer @ 2020-04-04 20:19:03

抱灵++


by Custlo0793 @ 2020-04-04 20:19:29

话说泥萌这群抄袭神帖的有什么NB


by lndjy @ 2020-04-04 20:19:43

@happydef 现在蒟蒻都切Ynoi了,没有办法啊


by YUYGFGG @ 2020-04-04 20:20:48

你不说我都快忘了这个神贴


| 下一页