萌新太难了救救孩子吧

P2572 [SCOI2010] 序列操作

_CHO @ 2020-03-02 11:18:38

RT，样例过了，并且找到了数据（luogu不提供数据自己找的），手动测了前两个点，都是正确的QAQ，但是交上去就是0分WA，哪里出了问题啊/kk

#include <bits/stdc++.h>
using namespace std;
struct Tree{
    int max,lmax,rmax,tot;
};
const int maxn = 1e+5+100;
int n,m;
int a[maxn];
int sumv1[maxn<<2],sumv0[maxn<<2];
int maxv1[maxn<<2],maxv0[maxn<<2];
int lmaxv1[maxn<<2],lmaxv0[maxn<<2];
int rmaxv1[maxn<<2],rmaxv0[maxn<<2];
int tot1[maxn<<2],tot0[maxn<<2];
int setv[maxn<<2],turnv[maxn<<2];
inline int run_lmaxv1(int o){
    int cur=0;
    cur=lmaxv1[o<<1];
    if(tot1[o<<1]) cur=tot1[o<<1]+lmaxv1[o<<1|1];
    return cur;
}
inline int run_lmaxv0(int o){
    int cur = 0;
    cur=lmaxv0[o<<1];
    if(tot0[o<<1])cur=tot0[o<<1]+lmaxv0[o<<1|1];
    return cur;
}
inline int run_rmaxv1(int o){
    int cur = 0;
    cur=rmaxv1[o<<1|1];
    if(tot1[o<<1|1]) cur = tot1[o<<1|1] + rmaxv1[o<<1];
    return cur;
}
inline int run_rmaxv0(int o){
    int cur = 0;
    cur=rmaxv0[o<<1|1];
    if(tot0[o<<1|1]) cur = tot0[o<<1|1] + rmaxv0[o<<1];
    return cur;
}
inline void pushup(int o){
    sumv1[o] = sumv1[o<<1]+sumv1[o<<1|1];
    sumv0[o] = sumv0[o<<1]+sumv0[o<<1|1];
    maxv1[o] = max(max(maxv1[o<<1],maxv1[o<<1|1]),rmaxv1[o<<1]+lmaxv1[o<<1|1]);
    maxv0[o] = max(max(maxv0[o<<1],maxv0[o<<1|1]),rmaxv0[o<<1]+rmaxv0[o<<1|1]);
    lmaxv1[o] = run_lmaxv1(o);
    lmaxv0[o] = run_lmaxv0(o);
    rmaxv1[o] = run_rmaxv1(o);
    rmaxv0[o] = run_rmaxv0(o);
    tot1[o] = (tot1[o<<1]&&tot1[o<<1|1])?(tot1[o<<1]+tot1[o<<1|1]):0;
    tot0[o] = (tot0[o<<1]&&tot0[o<<1|1])?(tot0[o<<1]+tot0[o<<1|1]):0;
}
inline void build(int o,int l,int r){
    setv[o] = -1;
    if(l==r){
        sumv1[o] = a[l]^0;
        sumv0[o] = a[l]^1;
        maxv1[o] = a[l]^0;
        maxv0[o] = a[l]^1;
        lmaxv1[o] = a[l]^0;
        lmaxv0[o] = a[l]^1;
        rmaxv1[o] = a[l]^0;
        rmaxv0[o] = a[l]^1;
        tot1[o] = a[l]^0;
        tot0[o] = a[l]^1;
        return ;
    }
    int mid=(l+r)>>1;
    build(o<<1,l,mid);
    build(o<<1|1,mid+1,r);
    pushup(o);
    return ;
}
//sumv maxv lmaxv rmaxv tot
inline void pushdown(int o,int l,int r){
    int mid = (l+r)>>1;
    if(setv[o]!=-1){
        setv[o<<1] = setv[o];
        setv[o<<1|1] = setv[o];
        turnv[o<<1] = 0;
        turnv[o<<1|1] = 0;
        sumv1[o<<1] = (mid-l+1)*(0^setv[o]);
        sumv0[o<<1] = (mid-l+1)*(1^setv[o]);
        maxv1[o<<1] = (mid-l+1)*(0^setv[o]);
        maxv0[o<<1] = (mid-l+1)*(1^setv[o]);
        lmaxv1[o<<1] = (mid-l+1)*(0^setv[o]);
        lmaxv0[o<<1] = (mid-l+1)*(1^setv[o]);
        rmaxv1[o<<1] = (mid-l+1)*(0^setv[o]);
        rmaxv0[o<<1] = (mid-l+1)*(1^setv[o]);
        tot1[o<<1] = (mid-l+1)*(0^setv[o]);
        tot0[o<<1] = (mid-l+1)*(1^setv[o]);
        sumv1[o<<1|1] = (r-mid)*(0^setv[o]);
        sumv0[o<<1|1]= (r-mid)*(1^setv[o]);
        maxv1[o<<1|1] = (r-mid)*(0^setv[o]);
        maxv0[o<<1|1] = (r-mid)*(1^setv[o]);
        lmaxv1[o<<1|1] = (r-mid)*(0^setv[o]);
        lmaxv0[o<<1|1] = (r-mid)*(1^setv[o]);
        rmaxv1[o<<1|1] = (r-mid)*(0^setv[o]);
        rmaxv0[o<<1|1] = (r-mid)*(1^setv[o]);
        tot1[o<<1|1] = (r-mid)*(0^setv[o]);
        tot0[o<<1|1] = (r-mid)*(1^setv[o]);
    }
    else if(turnv[o]){
        if(setv[o<<1]!=-1) setv[o<<1] ^= turnv[o];
        else turnv[o<<1] ^= turnv[o];
        if (setv[o<<1|1]!=-1) setv[o<<1|1]^=turnv[o];
        else turnv[o<<1|1]^=turnv[o];
        swap(sumv1[o<<1|1],sumv0[o<<1|1]);
        swap(sumv1[o<<1],sumv0[o<<1]);
        swap(maxv1[o<<1|1],maxv0[o<<1|1]);
        swap(maxv1[o<<1],maxv0[o<<1]);
        swap(lmaxv1[o<<1|1],lmaxv0[o<<1|1]);
        swap(lmaxv1[o<<1],lmaxv0[o<<1]);
        swap(rmaxv1[o<<1|1],rmaxv0[o<<1|1]);
        swap(rmaxv1[o<<1],rmaxv0[o<<1]);
        swap(tot1[o<<1|1],tot0[o<<1|1]);
        swap(tot1[o<<1],tot0[o<<1]);
    }
    setv[o] = -1;
    turnv[o] = 0;
    return ;
}
inline void putsettag(int o,int l,int r,int v){
    int mid=(l+r)>>1;
    turnv[o] = 0;
    setv[o] = v;
    sumv1[o] = (r-l+1)*(v^0);
    sumv0[o] = (r-l+1)*(v^1);
    maxv1[o] = (r-l+1)*(v^0);
    maxv0[o] = (r-l+1)*(v^1);
    lmaxv1[o]= (r-l+1)*(v^0);
    lmaxv0[o]= (r-l+1)*(v^1);
    rmaxv1[o]= (r-l+1)*(v^0);
    rmaxv0[o]= (r-l+1)*(v^1);
    tot1[o]  = (r-l+1)*(v^0);
    tot0[o]  = (r-l+1)*(v^1);
    return ;
}
inline void optset(int o,int l,int r,int ql,int qr,int v){
    if(ql<=l&&r<=qr){
        putsettag(o,l,r,v);
        return ;
    }
    pushdown(o,l,r);
    int mid=(l+r)>>1;
    if(ql<=mid) optset(o<<1,l,mid,ql,qr,v);
    if(qr>mid) optset(o<<1|1,mid+1,r,ql,qr,v);
    pushup(o);
    return ;
}
inline void putturntag(int o,int l,int r){
    if(setv[o]!=-1) setv[o]^=1;
    else turnv[o] ^=1;
    swap(sumv1[o],sumv0[o]);
    swap(maxv1[o],maxv0[o]);
    swap(lmaxv1[o],lmaxv0[o]);
    swap(rmaxv1[o],rmaxv0[o]);
    swap(tot1[o],tot0[o]);
    return ;
}
inline void optturn(int o,int l,int r,int ql,int qr){
    if(ql<=l&&r<=qr){
        putturntag(o,l,r);
        return ;
    }
    pushdown(o,l,r);
    int mid=(l+r)>>1;
    if(ql<=mid) optturn(o<<1,l,mid,ql,qr);
    if(qr>mid) optturn(o<<1|1,mid+1,r,ql,qr);
    pushup(o);
    return ;
}
inline int querysum(int o,int l,int r,int ql,int qr){
    if(ql<=l&&r<=qr){
        return sumv1[o];
    }
    pushdown(o,l,r);
    int mid=(l+r)>>1;
    int ans=0;
    if(ql<=mid) ans=querysum(o<<1,l,mid,ql,qr);
    if(qr>mid) ans+=querysum(o<<1|1,mid+1,r,ql,qr);
    return ans;
}
inline Tree querymax(int o,int l,int r,int ql,int qr){
    Tree cur;
    if(ql<=l&&r<=qr){
        cur.max = maxv1[o];
        cur.lmax = lmaxv1[o];
        cur.rmax = rmaxv1[o];
        cur.tot= tot1[o];
        return cur;
    }
    pushdown(o,l,r);
    int mid = (l+r)>>1;
    if(ql>mid) return querymax(o<<1|1,mid+1,r,ql,qr);
    if(qr<=mid) return querymax(o<<1,l,mid,ql,qr);
    Tree ls= querymax(o<<1,l,mid,ql,qr);
    Tree rs = querymax(o<<1|1,mid+1,r,ql,qr);
    cur.lmax=max(ls.lmax,ls.tot?ls.tot+rs.lmax:0);
    cur.rmax=max(rs.rmax,rs.tot?rs.tot+ls.rmax:0);
    cur.max=max(max(ls.max,rs.max),ls.rmax+rs.lmax);
    cur.tot=(ls.tot&&rs.tot)?ls.tot+rs.tot:0;
    return cur;
}
int main(){
    //freopen("test.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(register int i=1;i<=n;++i) scanf("%d",a+i);
    build(1,1,n);
    while(m--){
        int opt,l,r;
        scanf("%d%d%d",&opt,&l,&r);
        ++l,++r;
        if(opt==0) optset(1,1,n,l,r,0);
        if(opt==1) optset(1,1,n,l,r,1);
        if(opt==2) optturn(1,1,n,l,r);
        if(opt==3) printf("%d\n",querysum(1,1,n,l,r));
        if(opt==4) printf("%d\n",querymax(1,1,n,l,r).max);
    }
    return 0;
}

by _CHO @ 2020-03-02 11:21:48

in

10 10
0 1 0 1 0 1 0 1 0 1 
4 1 7
4 0 9
2 8 8
0 4 5
1 1 7
2 1 5
1 6 7
3 2 4
1 2 2
0 6 8

out

1
1
0

这应该是第一个点，感觉输出和标准是一样的啊QAQ

by zhanghzqwq @ 2020-03-02 11:22:47

@今天非常难忘 Orz切紫题

by Callous_Murder @ 2020-03-02 11:27:01

这题我救不了你，我最恨线段树了

by BotDand @ 2020-03-02 11:37:41

不会啊Orz

by S1gMa @ 2020-03-02 11:37:49

qndmx

by stdout @ 2020-03-02 11:46:14

萌新切紫体orz

by CreeperLordVader @ 2020-03-02 12:04:56

给您一份AC代码对拍吧

#include<bits/stdc++.h>
using namespace std;
const int MAXN=100005;
int n,m,a[MAXN];
int setc[MAXN<<2],rmax[MAXN<<2][2];
int rev[MAXN<<2],lmax[MAXN<<2][2];
int sub[MAXN<<2][2],sum[MAXN<<2];
void read(int& x)
{
    char c=getchar();
    x=0;
    while(c<'0'||c>'9')c=getchar();
    while(c>='0'&&c<='9')
    {
        x=x*10+c-'0';
        c=getchar();
    }
}
void update(int o,int l,int r)
{
    int mid=(l+r)>>1;
    if(sum[o<<1]==mid-l+1)
    {
        lmax[o][1]=sum[o<<1]+lmax[o<<1|1][1];
        lmax[o][0]=0;
    }
    else lmax[o][1]=lmax[o<<1][1];
    if(!sum[o<<1])
    {
        lmax[o][0]=mid-l+1+lmax[o<<1|1][0];
        lmax[o][1]=0;
    }
    else lmax[o][0]=lmax[o<<1][0];
    if(sum[o<<1|1]==r-mid)
    {
        rmax[o][1]=sum[o<<1|1]+rmax[o<<1][1];
        rmax[o][0]=0;
    }
    else rmax[o][1]=rmax[o<<1|1][1];
    if(!sum[o<<1|1])
    {
        rmax[o][0]=r-mid+rmax[o<<1][0];
        rmax[o][1]=0;
    }
    else rmax[o][0]=rmax[o<<1|1][0];
    sub[o][1]=max(max(sub[o<<1][1],sub[o<<1|1][1]),rmax[o<<1][1]+lmax[o<<1|1][1]);
    sub[o][0]=max(max(sub[o<<1][0],sub[o<<1|1][0]),rmax[o<<1][0]+lmax[o<<1|1][0]);
    sum[o]=sum[o<<1]+sum[o<<1|1];
}
void pushdown(int o,int l,int r)
{
    int mid=(l+r)>>1;
    if(setc[o]>=0)
    {
        rev[o]=rev[o<<1]=rev[o<<1|1]=0;
        setc[o<<1]=setc[o];
        setc[o<<1|1]=setc[o];
        if(setc[o])
        {
            sub[o<<1][0]=lmax[o<<1][0]=rmax[o<<1][0]=0;
            sum[o<<1]=lmax[o<<1][1]=rmax[o<<1][1]=sub[o<<1][1]=mid-l+1;
            sub[o<<1|1][0]=lmax[o<<1|1][0]=rmax[o<<1|1][0]=0;
            sum[o<<1|1]=lmax[o<<1|1][1]=rmax[o<<1|1][1]=sub[o<<1|1][1]=r-mid;
        }
        else
        {
            sub[o<<1][1]=lmax[o<<1][1]=rmax[o<<1][1]=0;
            sum[o<<1]=0;
            lmax[o<<1][0]=rmax[o<<1][0]=sub[o<<1][0]=mid-l+1;
            lmax[o<<1][1]=rmax[o<<1][1]=sub[o<<1][1]=0;
            sub[o<<1|1][1]=lmax[o<<1|1][1]=rmax[o<<1|1][1]=0;
            sum[o<<1|1]=0;
            lmax[o<<1|1][0]=rmax[o<<1|1][0]=sub[o<<1|1][0]=r-mid;
            lmax[o<<1|1][1]=rmax[o<<1|1][1]=sub[o<<1|1][1]=0;
        }
        setc[o]=-1;
    }
    if(rev[o])
    {
        rev[o<<1]^=1;
        rev[o<<1|1]^=1;
        if(setc[o<<1]>=0)setc[o<<1]^=1;
        if(setc[o<<1|1]>=0)setc[o<<1|1]^=1;
        sum[o<<1]=mid-l+1-sum[o<<1];
        sum[o<<1|1]=r-mid-sum[o<<1|1];
        swap(sub[o<<1][0],sub[o<<1][1]);
        swap(sub[o<<1|1][0],sub[o<<1|1][1]);
        swap(lmax[o<<1][0],lmax[o<<1][1]);
        swap(rmax[o<<1][0],rmax[o<<1][1]);
        swap(lmax[o<<1|1][0],lmax[o<<1|1][1]);
        swap(rmax[o<<1|1][0],rmax[o<<1|1][1]);
        rev[o]=0;
    }
}
void build(int o,int l,int r)
{
    if(l==r)
    {
        sum[o]=a[l];
        if(a[l])sub[o][1]=lmax[o][1]=rmax[o][1]=1;
        else sub[o][0]=lmax[o][0]=rmax[o][0]=1;
        return ;
    }
    int mid=(l+r)>>1;
    build(o<<1,l,mid);
    build(o<<1|1,mid+1,r);
    update(o,l,r);
}
void change(int o,int l,int r,int ql,int qr,int k)
{
    if(ql<=l&&qr>=r)
    {
        sub[o][k]=lmax[o][k]=rmax[o][k]=r-l+1;
        sub[o][k^1]=lmax[o][k^1]=rmax[o][k^1]=0;
        sum[o]=(r-l+1)*k;
        setc[o]=k;
        rev[o]=0;
        return ;
    }
    int mid=(l+r)>>1;
    pushdown(o,l,r);
    if(ql<=mid)change(o<<1,l,mid,ql,qr,k);
    if(qr>mid)change(o<<1|1,mid+1,r,ql,qr,k);
    update(o,l,r);
}
void flip(int o,int l,int r,int ql,int qr)
{
    if(ql<=l&&qr>=r)
    {
        sum[o]=r-l+1-sum[o];
        swap(lmax[o][0],lmax[o][1]);
        swap(rmax[o][0],rmax[o][1]);
        swap(sub[o][0],sub[o][1]);
        rev[o]^=1;
        setc[o]^=1;
        return ;
    }
    int mid=(l+r)>>1;
    pushdown(o,l,r);
    if(ql<=mid)flip(o<<1,l,mid,ql,qr);
    if(qr>mid)flip(o<<1|1,mid+1,r,ql,qr);
    update(o,l,r);
}
int qsum(int o,int l,int r,int ql,int qr)
{
    if(ql<=l&&qr>=r)
    {
        return sum[o];
    }
    int mid=(l+r)>>1,ans=0;
    pushdown(o,l,r);
    if(ql<=mid)ans+=qsum(o<<1,l,mid,ql,qr);
    if(qr>mid)ans+=qsum(o<<1|1,mid+1,r,ql,qr);
    return ans;
}
int query(int o,int l,int r,int ql,int qr)
{
    if(ql<=l&&qr>=r)
    {
        return sub[o][1];
    }
    int mid=(l+r)>>1,ansl=-1,ansr=-1,lans=-1,rans=-1;
    pushdown(o,l,r);
    if(ql<=mid)
    {
        ansl=query(o<<1,l,mid,ql,qr);
        if(qr>mid)lans=min(rmax[o<<1][1],mid-ql+1);
    }
    if(qr>mid)
    {
        ansr=query(o<<1|1,mid+1,r,ql,qr);
        if(ql<=mid)rans=min(lmax[o<<1|1][1],qr-mid);
    }
    return max(max(ansl,ansr),lans+rans);
}
int main()
{
    read(n);
    read(m);
    for(int i=1;i<=n;i++)
    {
        read(a[i]);
    }
    build(1,1,n);
    memset(setc,-1,sizeof(setc));
    for(int i=1;i<=m;i++)
    {
        int op,l,r;
        read(op);
        read(l);
        read(r);
        l++;
        r++;
        switch(op)
        {
            case 0:
            {
                change(1,1,n,l,r,0);
                break;
            }
            case 1:
            {
                change(1,1,n,l,r,1);
                break;
            }
            case 2:
            {
                flip(1,1,n,l,r);
                break;
            }
            case 3:
            {
                printf("%d\n",qsum(1,1,n,l,r));
                break;
            }
            case 4:
            {
                printf("%d\n",query(1,1,n,l,r));
                break;
            }
        }
    }
}
|