吴隐 @ 2019-12-03 15:01:07

by 吴隐 @ 2019-12-03 15:02:11

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
#define Main main
#define Gc() getchar()
#define ls pt<<1
#define rs pt<<1|1
#define rint register int
#define iint inline int
#define void inline void
iint Read(){int x=0;char c=Gc();while(c<'0'||c>'9')c=Gc();while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+c-'0',c=Gc();return x;}
void Writ(int x){if(x>9)Writ(x/10);putchar(x%10+'0');return;}
void Print(int x){Writ(x),putchar('\n');}
iint Max(int a,int b,int c){return max(a,max(b,c));}
struct Tree{int l,r,sum[2],llen[2],rlen[2],len[2],tg,re;}tr[800005];
int n,m,a[200005];
Tree Update(Tree pt,Tree le,Tree ri)
{
    for(rint i=0;i<2;i++)
        pt.len[i]=Max(le.len[i],ri.len[i],le.rlen[i]+ri.llen[i]),
        pt.llen[i]=le.llen[i]+ri.llen[i]*(!le.sum[i^1]),
        pt.rlen[i]=ri.rlen[i]+le.rlen[i]*(!ri.sum[i^1]),
        pt.sum[i]=le.sum[i]+ri.sum[i];return pt;
}
void Spread(int pt)
{
    Tree t=tr[pt],lt=tr[ls],rt=tr[rs];
    int lsi=lt.r-lt.l+1,rsi=rt.r-rt.l+1;
    if(t.tg!=-1)
    {
        int l1=lsi*(t.tg^1),l2=lsi*t.tg,r1=rsi*(t.tg^1),r2=rsi*t.tg;
        lt=tr[ls]=(Tree){lt.l,lt.r,{l1,l2},{l1,l2},{l1,l2},{l1,l2},t.tg,0};
        rt=tr[rs]=(Tree){rt.l,rt.r,{r1,r2},{r1,r2},{r1,r2},{r1,r2},t.tg,0};
        t.tg=tr[pt].tg=-1;t.re=tr[pt].re=0;
    }
    if(t.re)
    {
        lt=tr[ls]=(Tree){lt.l,lt.r,{lt.sum[1],lt.sum[0]},{lt.llen[1],lt.llen[0]},{lt.rlen[1],lt.rlen[0]},{lt.len[1],lt.len[0]},lt.tg,lt.re};
        rt=tr[rs]=(Tree){rt.l,rt.r,{rt.sum[1],rt.sum[0]},{rt.llen[1],rt.llen[0]},{rt.rlen[1],rt.rlen[0]},{rt.len[1],rt.len[0]},rt.tg,rt.re};
        if(tr[ls].tg!=-1)tr[ls].tg^=1;else{tr[ls].re^=1;}if(tr[rs].tg!=-1)tr[rs].tg^=1;else{tr[rs].re^=1;}tr[pt].re=0;
    }return;
}
void Build(int pt,int le,int ri)
{
    tr[pt].l=le,tr[pt].r=ri;int mid=(le+ri)>>1;
    if(le==ri){tr[pt]=(Tree){le,ri,{a[le]^1,a[le]},{a[le]^1,a[le]},{a[le]^1,a[le]},{a[le]^1,a[le]},-1,0};return;}
    Build(ls,le,mid);Build(rs,mid+1,ri);tr[pt]=Update(tr[pt],tr[ls],tr[rs]);tr[pt].tg=-1;tr[pt].re=0;
}
void Memset(int pt,int le,int ri,int sg)
{
    int l=tr[pt].l,r=tr[pt].r,si=r-l+1,s1=si*(sg^1),s2=si*sg;
    if(le<=l&&ri>=r){tr[pt]=(Tree){l,r,{s1,s2},{s1,s2},{s1,s2},{s1,s2},sg,0};return;}
    int mid=(l+r)>>1;Spread(pt);
    if(mid>=le)Memset(ls,le,ri,sg);
    if(mid<ri)Memset(rs,le,ri,sg);
    tr[pt]=Update(tr[pt],tr[ls],tr[rs]);
}
void Reverse(int pt,int le,int ri)
{
    Tree t=tr[pt];int l=t.l,r=t.r;
    if(le<=l&&ri>=r)
    {
        tr[pt]=(Tree){l,r,{t.sum[1],t.sum[0]},{t.llen[1],t.llen[0]},{t.rlen[1],t.rlen[0]},{t.len[1],t.len[0]},t.tg,t.re};
        if(t.tg!=-1)tr[pt].tg^=1;else{tr[pt].re^=1;}return;
    }int mid=(l+r)>>1;Spread(pt);
    if(mid>=le)Reverse(ls,le,ri);
    if(mid<ri)Reverse(rs,le,ri);
    tr[pt]=Update(tr[pt],tr[ls],tr[rs]);
}
Tree Query(int pt,int le,int ri)
{
    Tree t=tr[pt],L,R,res;int l=t.l,r=t.r,mid=(l+r)>>1;
    res=L=R=(Tree){0,0,{0,0},{0,0},{0,0},{0,0},-1,0};
    if(le<=l&&ri>=r){return t;}Spread(pt);
    if(mid>=le)L=Query(ls,le,ri);
    if(mid<ri)R=Query(rs,le,ri);
    return Update(res,L,R);
}
signed Main()
{
    n=Read();m=Read();
    for(rint i=1;i<=n;i++)
    a[i]=Read();Build(1,1,n);
    for(rint i=1;i<=m;i++)
    {
        int sg=Read(),l=Read()+1,r=Read()+1;
        if(sg<2)Memset(1,l,r,sg);else
        if(sg==2)Reverse(1,l,r);else
        if(sg==3)Print(Query(1,l,r).sum[1]);else
        if(sg==4)Print(Query(1,l,r).len[1]);
    }return 0;
}

by 吴隐 @ 2019-12-03 15:03:52

测评记录R28057749

bzoj RunID 3405554

by 唐晨成 @ 2019-12-03 16:26:59

你个菜鸡

by 唐晨成 @ 2019-12-03 16:27:28

我用屁股都能打完这个代码

by nkinclude @ 2019-12-06 12:57:41

2333

by Haishu @ 2019-12-06 19:47:18

@吴隐 lz现在改对了吗？我也是bzojAC洛谷WA0

by WrongAnwser @ 2019-12-06 21:43:37

我也是，错的一样

先打了一个线段树再打了个珂朵莉结果错的一样

当然珂朵莉恰了氧气也T了来着

珂朵莉 线段树

by 吴隐 @ 2019-12-07 09:42:51

sg有可能大于四！！！

我*&%￥#￥&……%￥%…￥…%&&

已AC

by STPGUY @ 2020-02-04 21:52:28

@吴隐 SG大于4该怎么处理呢