能过样例,但是全wa

P2572 [SCOI2010] 序列操作

qwq2519 @ 2020-11-05 22:05:54

#include<bits/stdc++.h>
#define rep(i,j,k) for(register int i(j);i<=k;++i)
using namespace std;
typedef long long lxl;
typedef pair<int,int> pii;
inline char gt()
{
    static char buf[100000],*p1=buf,*p2=buf;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
template <typename T>
inline void  read(T &x)
{
    register char ch=gt();
    x=0;
    int w(0);
    while(!(ch>='0'&&ch<='9'))w|=ch=='-',ch=gt();
    while(ch>='0'&&ch<='9')x=x*10+(ch&15),ch=gt();
    w?x=~(x-1):x;
}
template <typename T>
inline void out(T x)
{
    if(x<0) x=-x,putchar('-');
    char ch[20];
    int num(0);
    while(x||!num) ch[++num]=x%10+'0',x/=10;
    while(num) putchar(ch[num--]);
    putchar('\n');
}
const int N=1e5+79;
int n,m;
int a[N];

inline int max(int a,int b)
{
    return a>b?a:b;
}
struct node
{
    int len,lmax,rmax,maxx,sum;
    node() {}
    node(int a,int b,int c,int d,int e)
    {
        len=a;
        lmax=b;
        rmax=c;
        maxx=d;
        sum=e;
    }
};
struct Segmentree
{
    int lc[N<<2],rc[N<<2],lazy[N<<2],sum[N<<2],rev[N<<2];
    int root,cnt;
    int maxx[N<<2][2],lmax[N<<2][2],rmax[N<<2][2];
    Segmentree()
    {
        memset(lazy,-1,sizeof lazy);
    }

    inline void pushup(int p,int L,int R)
    {
        sum[p]=sum[lc[p]]+sum[rc[p]];
        int mid((L+R)>>1);

        if(sum[lc[p]]==mid-L+1)
            lmax[p][1]=mid-L+1+lmax[rc[p]][1];
        else  lmax[p][1]=lmax[lc[p]][1];

        if(sum[lc[p]]==0)
            lmax[p][0]=mid-L+1+rmax[rc[p]][0];
        else lmax[p][0]=lmax[lc[p]][0];

        if(sum[rc[p]]==R-mid)
            rmax[p][1]=R-mid+rmax[lc[p]][1];
        else rmax[p][1]=rmax[rc[p]][1];

        if(sum[rc[p]]==0)
            rmax[p][0]=R-mid+rmax[rc[p]][0];
        else rmax[p][0]=rmax[rc[p]][0];

        maxx[p][1]=max(max( maxx[lc[p]][1],maxx[rc[p]][1]),rmax[lc[p]][1]+lmax[rc[p]][1]);
        maxx[p][0]=max(max( maxx[lc[p]][1],maxx[rc[p]][0]),rmax[lc[p]][0]+lmax[rc[p]][0]);
    }
    inline void pushdown(int p,int L,int R)
    {
        if(!lc[p]) lc[p]=++cnt;
        if(!rc[p]) rc[p]=++cnt;
        int mid((L+R)>>1);
        if(lazy[p]!=-1)
            {
                rev[p]=0;//Ô­±¾Òª·­×ª£¬²»Óã»1
                sum[lc[p]]=(mid-L+1)*lazy[p];
                sum[rc[p]]=(R-mid)*lazy[p];

                lazy[lc[p]]=lazy[rc[p]]=lazy[p];
                rev[lc[p]]=rev[rc[p]]=0;

                maxx[lc[p]][lazy[p]]=lmax[lc[p]][lazy[p]]=rmax[lc[p]][lazy[p]]=mid-L+1;
                maxx[lc[p]][lazy[p]^1]=lmax[lc[p]][lazy[p]^1]=rmax[lc[p]][lazy[p]^1]=0;

                maxx[rc[p]][lazy[p]]=lmax[rc[p]][lazy[p]]=rmax[rc[p]][lazy[p]]=R-mid;
                maxx[rc[p]][lazy[p]^1]=lmax[rc[p]][lazy[p]^1]=rmax[rc[p]][lazy[p]^1]=0;

                lazy[p]=-1;
            }
        if(rev[p])
            {
                sum[lc[p]]=(mid-L+1)-sum[lc[p]];
                sum[rc[p]]=(R-mid)-sum[rc[p]];

                if(lazy[lc[p]]!=-1) lazy[lc[p]]^=1;
                else rev[lc[p]]^=1;
                if(lazy[rc[p]]!=-1) lazy[rc[p]]^=1;
                else rev[rc[p]]^=1;

                swap(maxx[lc[p]][0],maxx[lc[p]][1]);
                swap(lmax[lc[p]][0],lmax[lc[p]][1]);
                swap(rmax[lc[p]][0],rmax[lc[p]][1]);

                swap(maxx[rc[p]][0],maxx[rc[p]][1]);
                swap(lmax[rc[p]][0],lmax[rc[p]][1]);
                swap(rmax[rc[p]][0],rmax[rc[p]][1]);
                rev[p]=0;
            }
    }

    inline void build(int &p,int L,int R)
    {
        if(!p) p=++cnt;
        if(L==R)
            {
                sum[p]=a[L];
                if(a[L])
                    maxx[p][1]=lmax[p][1]=rmax[p][1]=1;
                else maxx[p][0]=lmax[p][0]=rmax[p][0]=1;
                return ;
            }
        int mid((L+R)>>1);
        build(lc[p],L,mid);
        build(rc[p],mid+1,R);
        pushup(p,L,R);
    }
    inline void change(int p,int L,int R,int ll,int rr,int op)
    {
        pushdown(p,L,R);

        if(ll<=L&&rr>=R)
            {
                if(op==1||op==0)
                    {
                        sum[p]=(R-L+1)*op;
                        lazy[p]=op;
                        maxx[p][lazy[p]]=lmax[p][lazy[p]]=rmax[p][lazy[p]]=R-L+1;
                        maxx[p][lazy[p]^1]=lmax[p][lazy[p]^1]=rmax[p][lazy[p]^1]=0;
                    }
                else
                    {
                        sum[p]=(R-L+1)-sum[p];
                        rev[p]^=1;
                        swap(maxx[p][1],maxx[p][0]);
                        swap(lmax[p][1],lmax[p][0]);
                        swap(rmax[p][1],rmax[p][0]);
                    }
                return ;
            }
        int mid((L+R)>>1);
        if(ll<=mid) change(lc[p],L,mid,ll,rr,op);
        if(rr>mid) change(rc[p],mid+1,R,ll,rr,op);
        pushup(p,L,R);
    }
    inline int querysum(int p,int L,int R,int ll,int rr)
    {

        if(!p) return 0;
        pushdown(p,L,R);
        if(ll<=L&&rr>=R) return sum[p];
        int mid((L+R)>>1);
        int val(0);
        if(ll<=mid) val+=querysum(lc[p],L,mid,ll,rr);
        if(rr>mid) val+=querysum(rc[p],mid+1,R,ll,rr);
        return val;
    }

    inline node querymax(int p,int L,int R,int ll,int rr)
    {
        pushdown(p,L,R);
//      if(!p) return 0;
        if(ll<=L&&rr>=R) return node
                                    ((R-L+1),lmax[p][1],rmax[p][1],maxx[p][1],sum[p]);
        int mid((L+R)>>1);
        int val(-1);
        if(rr<=mid) return querymax(lc[p],L,mid,ll,rr);
        else if(ll>mid) return querymax(rc[p],mid+1,R,ll,rr);
        else
            {
                node lnum=querymax(lc[p],L,mid,ll,rr);
                node rnum=querymax(rc[p],mid+1,R,ll,rr);
                node ans;
                ans.sum=lnum.sum+rnum.sum;

                if(lnum.sum==lnum.len)
                    ans.lmax=lnum.sum+rnum.lmax;
                else ans.lmax=lnum.lmax;

                if(rnum.sum==rnum.len)
                    ans.rmax=rnum.sum+lnum.rmax;
                else ans.rmax=rnum.rmax;

                ans.maxx=max(lnum.rmax+rnum.lmax,max(lnum.maxx,rnum.maxx));
                return ans;
            }
    }
} S;

int main()
{

    cin>>n>>m;
    rep(i,1,n) cin>>a[i];
    S.build(S.root,1,n);
    int op,l,r;
    while(m--)
        {
            cin>>op>>l>>r;
            l++;
            r++;
            if(op==0) S.change(S.root,1,n,l,r,0);
            else if(op==1) S.change(S.root,1,n,l,r,1);
            else if(op==2) S.change(S.root,1,n,l,r,2);
            else if(op==3) cout<<S.querysum(S.root,1,n,l,r)<<endl;
            else cout<<S.querymax(S.root,1,n,l,r).maxx<<endl;
        }
    return 0;
}

求助


by qwq2519 @ 2020-11-05 22:06:13

不该在考前作死写的。。。心态BOOM


|