求助啊!!!救救孩子!!!

P2572 [SCOI2010] 序列操作

CreeperLordVader @ 2019-03-09 19:16:21

问题很奇怪

为什么加了调试语句以后答案就成了对的

不加就是错的??

数据:


20 6
1 0 1 0 1 1 1 0 1 0 1 1 0 0 1 0 0 0 0 1
1 7 11
2 4 19
2 12 13
4 16 18
0 9 9
3 5 10

最后一个询问应输出0,我输出2

但是对操作1加上调试语句后答案就又变成了0


#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;
        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)
    {
        if(k)
        {
            sub[o][1]=lmax[o][1]=rmax[o][1]=r-l+1;
            sub[o][0]=lmax[o][0]=rmax[o][0]=0;
        }
        else
        {
            sub[o][0]=lmax[o][0]=rmax[o][0]=r-l+1;
            sub[o][1]=lmax[o][1]=rmax[o][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;
        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);
}
void debug()
{
    for(int i=1;i<=n;i++)
        cout<<qsum(1,1,n,i,i)<<" ";
    cout<<endl;
}
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);
//              debug();
                break;
            }
            case 1:
            {
                change(1,1,n,l,r,1);
//              debug();
                break;
            }
            case 2:
            {
                flip(1,1,n,l,r);
//              debug();
                break;
            }
            case 3:
            {
//              debug();
                printf("%d\n",qsum(1,1,n,l,r));
                break;
            }
            case 4:
            {
                printf("%d\n",query(1,1,n,l,r));
                break;
            }
        }
    }
}
/*
20 6
1 0 1 0 1 1 1 0 1 …

by hsfzLZH1 @ 2019-03-09 20:10:34

@CreeperLordVader 您没有及时 pushdown


by CreeperLordVader @ 2019-03-09 20:14:36

@hsfzLZH1

我也怀疑是这样

但我看了每个地方都有PUSHDOWN啊


by hsfzLZH1 @ 2019-03-09 20:17:10

@CreeperLordVader 那您有没有都写 update 呢?


by CreeperLordVader @ 2019-03-09 20:21:31

@hsfzLZH1

修改都写了,查询函数没写,但那个也没必要

而且都写UPDATE以后结果一样


|