样例过了但全WA,毒瘤了一上午了,求助

P2572 [SCOI2010] 序列操作

一只退役蒟蒻 @ 2020-08-10 14:20:44

#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdio>
#include<cmath>
#define LL long long
using namespace std;
int read()
{
    int s=0,bj=0;
    char ch=getchar();
    while(ch<'0'||ch>'9')bj|=(ch=='-'),ch=getchar();
    while(ch>='0'&&ch<='9')s=(s<<1)+(s<<3)+(ch^48),ch=getchar();
    return bj?-s:s;
}
void printnum(int x)
{
    if(x>9)printnum(x/10);
    putchar(x%10^48);
}
void print(int x,char ch)
{
    if(x<0){putchar('-');x=-x;}
    printnum(x);putchar(ch);
}
int n,m;
bool a[100005];int id[100005],K;
int L[405],R[405];
int ls[405],rs[405],sum[405],maxx[405];//1的系列 
int LS[405],RS[405],MAXX[405],SUM[405];//0的系列 
int rev[405],bj[405];//翻转标记,覆盖标记 
void pushdown(int x)
{
    int ll=L[x],rr=R[x];
    if(~bj[x])
    {
        for(int i=ll;i<=rr;++i)a[i]=bj[x];
        bj[x]=-1;rev[x]=0;
    }
    else if(rev[x])
    {
        for(int i=ll;i<=rr;++i)a[i]^=1;
        rev[x]=0;
    }
}
void Get(int x)
{
    int ll=L[x],rr=R[x],tmp,tot;maxx[x]=MAXX[x]=0;
    tmp=0;for(int i=ll;i<=rr;++i)if(a[i])++tmp;else break;ls[x]=tmp;
    tmp=0;for(int i=rr;i>=ll;--i)if(a[i])++tmp;else break;rs[x]=tmp;
    tmp=0;for(int i=ll;i<=rr;++i)if(!a[i])++tmp;else break;LS[x]=tmp;
    tmp=0;for(int i=rr;i>=ll;--i)if(!a[i])++tmp;else break;RS[x]=tmp;
    tmp=0;tot=0;
    for(int i=ll;i<=rr;++i)if(a[i]==1){++tmp;++tot;}else {maxx[x]=max(maxx[x],tmp);tmp=0;}
    sum[x]=tot;maxx[x]=max(maxx[x],tmp);
    tmp=0;tot=0;
    for(int i=ll;i<=rr;++i)if(!a[i]){++tmp;++tot;}else {MAXX[x]=max(MAXX[x],tmp);tmp=0;}
    SUM[x]=tot;MAXX[x]=max(MAXX[x],tmp);
}
void Sol(int l,int r,int bj)
{
    if(bj^2)for(int i=l;i<=r;++i)a[i]=bj;
    else for(int i=l;i<=r;++i)a[i]^=1;
    Get(id[l]);
}
void Change(int num,int l,int r)
{
    int idl=id[l],idr=id[r];
    pushdown(idl);pushdown(idr);
    if(idl==idr){Sol(l,r,num);return;}
    Sol(l,R[idl],num);Sol(L[idr],r,num);
    for(int i=idl+1;i<=idr-1;++i)
    {
        ls[i]=rs[i]=maxx[i]=sum[i]=num?R[i]-L[i]+1:0;
        LS[i]=RS[i]=MAXX[i]=SUM[i]=num?0:R[i]-L[i]+1;
        rev[i]=0;bj[i]=num;
    }
}
void Sol_rev(int l,int r)
{
    int idl=id[l],idr=id[r];
    pushdown(idl);pushdown(idr);
    if(idl==idr){Sol(l,r,2);return;}
    Sol(l,R[idl],2);Sol(L[idr],r,2);
    for(int i=idl+1;i<=idr-1;++i)
    {
        if(~bj[i])bj[i]^=1;//前面已经覆盖为某个值,整体取反 
        else rev[i]^=1;
        swap(ls[i],LS[i]);swap(rs[i],RS[i]);swap(sum[i],SUM[i]);swap(maxx[i],MAXX[i]);
    }
}
int Ask_sum(int l,int r)
{
    int idl=id[l],idr=id[r],ans=0;
    pushdown(idl);pushdown(idr);
    if(idl==idr){for(int i=l;i<=r;++i)if(a[i])++ans;return ans;}
    for(int i=l;i<=R[idl];++i)if(a[i])++ans;
    for(int i=L[idr];i<=r;++i)if(a[i])++ans;
    for(int i=idl+1;i<=idr-1;++i)ans+=sum[i];
    return ans;
}
int Ask_len(int l,int r)
{
    int idl=id[l],idr=id[r],cnt=0,Maxx=0;
    int lst=0;
    pushdown(idl);pushdown(idr);
    if(idl==idr){for(int i=l;i<=r;++i)if(a[i])++cnt;else {Maxx=max(Maxx,cnt);cnt=0;}return max(Maxx,cnt);}
    for(int i=R[idl];i>=l;--i)if(a[i])++lst;else break;
    for(int i=idl+1;i<=idr-1;++i)
    {
        lst+=ls[i];
        Maxx=max(Maxx,lst);
        if(maxx[i]^(R[i]-L[i]+1))lst=0;
        if(!lst)lst=rs[i];
        Maxx=max(Maxx,ls[i]);
    }
    for(int i=l;i<=R[idl];++i)if(a[i])++cnt;else {Maxx=max(Maxx,cnt);cnt=0;}
    Maxx=max(Maxx,cnt);cnt=0;
    for(int i=L[idr];i<=r;++i)if(a[i])++cnt;else {Maxx=max(Maxx,cnt);cnt=0;}
    Maxx=max(Maxx,cnt);cnt=0;
    for(int i=L[idr];i<=r;++i)if(a[i])++cnt;else break;
    return max(Maxx,lst+cnt);
}
int main()
{
//  freopen("9.in","r",stdin);
//  freopen("99.out","w",stdout);
    n=read();m=read();K=sqrt(n);
    for(int i=1;i<=n;++i){a[i]=read();id[i]=(i-1)/K+1;}
    for(int i=1;i<=id[n];++i)bj[i]=-1;
    for(int i=1;i<=id[n];++i){L[i]=(i-1)*K+1;R[i]=min(i*K,n);Get(i);}
//  for(int i=1;i<=id[n];++i)cout<<ls[i]<<" "<<rs[i]<<" "<<sum[i]<<" "<<maxx[i]<<" "<<LS[i]<<" "<<RS[i]<<" "<<SUM[i]<<" "<<MAXX[i]<<endl;
    int opt,l,r;
    for(int i=1;i<=m;++i)
    {
        opt=read();l=read()+1;r=read()+1;
        if(!opt)Change(0,l,r);
        else if(opt==1)Change(1,l,r);
        else if(opt==2)Sol_rev(l,r);
        else if(opt==3)print(Ask_sum(l,r),'\n');
        else print(Ask_len(l,r),'\n');
//      for(int j=1;j<=id[n];++j)pushdown(j);
//      for(int i=1;i<=n;++i)cout<<a[i]<<" ";cout<<endl;
    }
    return 0;
}

by 一只退役蒟蒻 @ 2020-08-10 14:21:47

大概是4操作锅了,有的4操作莫名输出0QAQ


by NXYorz @ 2020-08-10 14:22:50

qwq


by 一只退役蒟蒻 @ 2020-08-10 14:23:24

@NXYorz 线段树pushdown/pushup太毒瘤了,写的分块qwq


by wbt0910 @ 2021-08-26 10:49:26

1202年调0202年自己的代码祭QAQ


|