大佬求助,完全找不到哪错

P2572 [SCOI2010] 序列操作

Iowa_BattleShip @ 2018-03-13 21:28:32

#include<cstdio>
using namespace std;
const int N=1e5+10;
struct co{
    int x,y,s;
    co()
    {
        x=s=y=0;
    }
};
co o_1[N<<2],o_0[N<<2],o;
int a[N],s[N<<2],ch[N<<2];
bool xo[N<<2];
int re()
{
    int x=0;
    char c=getchar();
    for(;c<'0'||c>'9';c=getchar());
    for(;c>='0'&&c<='9';c=getchar())
        x=x*10+(c-'0');
    return x;
}
void pp(int r)
{
    int lx=r<<1,ly=r<<1|1;
    s[r]=s[lx]+s[ly];
    if(o_1[lx].y==o_1[ly].x-1)
    {
        o_1[r].s=o_1[lx].s+o_1[ly].s;
        o_1[r].x=o_1[lx].x;
        o_1[r].y=o_1[ly].y;
    }
    else
        if(o_1[lx].s>o_1[ly].s)
            o_1[r]=o_1[lx];
        else
            o_1[r]=o_1[ly];
    if(o_0[lx].y==o_0[ly].x-1)
    {
        o_0[r].s=o_0[lx].s+o_0[ly].s;
        o_0[r].x=o_0[lx].x;
        o_0[r].y=o_0[ly].y;
    }
    else
        if(o_0[lx].s>o_0[ly].s)
            o_0[r]=o_0[lx];
        else
            o_0[r]=o_0[ly];
}
void pn(int r,int x,int y)
{
    int mid=(x+y)>>1,lx=r<<1,ly=r<<1|1,sl=mid-x+1,sr=y-mid,k=ch[r];
    if(k)
    {
        ch[lx]=ch[ly]=k;
        xo[lx]=xo[ly]=0;
        if(k==1)
        {
            s[lx]=sl;
            s[ly]=sr;
            o_1[lx].s=sl;
            o_1[lx].x=x;
            o_1[lx].y=mid;
            o_1[ly].s=sr;
            o_1[ly].x=mid+1;
            o_1[ly].y=y;
            o_0[lx].s=o_0[lx].x=o_0[lx].y=0;
            o_0[ly].s=o_0[ly].x=o_0[ly].y=0;
        }
        else
        {
            s[lx]=s[ly]=0;
            o_0[lx].s=sl;
            o_0[lx].x=x;
            o_0[lx].y=mid;
            o_0[ly].s=sr;
            o_0[ly].x=mid+1;
            o_0[ly].y=y;
            o_1[lx].s=o_1[lx].x=o_1[lx].y=0;
            o_1[ly].s=o_1[ly].x=o_1[ly].y=0;
        }
        ch[r]=0;
        return;
    }
    if(xo[r])
    {
        xo[lx]^=1;
        xo[ly]^=1;
        s[lx]=sl-s[lx];
        s[ly]=sr-s[ly];
        o=o_1[lx];
        o_1[lx]=o_0[lx];
        o_0[lx]=o;
        o=o_1[ly];
        o_1[ly]=o_0[ly];
        o_0[ly]=o;
        xo[r]=0;
    }
}
void bu(int r,int x,int y)
{
    int mid=(x+y)>>1;
    if(x==y)
    {
        s[r]=a[x];
        if(a[x])
        {
            o_1[r].s=1;
            o_1[r].x=o_1[r].y=x;
        }
        else
        {
            o_0[r].s=1;
            o_0[r].x=o_0[r].y=x;
        }
        return;
    }
    bu(r<<1,x,mid);
    bu(r<<1|1,mid+1,y);
    pp(r);
}
void fi(int r,int x,int y,int ql,int qr,int v)
{
    int mid=(x+y)>>1;
    if(ql<=x&&y<=qr)
    {
        if(!v)
        {
            ch[r]=-1;
            xo[r]=0;
            s[r]=0;
            o_0[r].s=y-x+1;
            o_0[r].x=x;
            o_0[r].y=y;
            o_1[r].s=o_1[r].x=o_1[r].y=0;
        }
        else
            if(v==1)
            {
                ch[r]=1;
                xo[r]=0;
                s[r]=y-x+1;
                o_1[r].s=y-x+1;
                o_1[r].x=x;
                o_1[r].y=y;
                o_0[r].s=o_0[r].x=o_0[r].y=0;
            }
            else
            {
                xo[r]^=1;
                s[r]=y-x+1-s[r];
                o=o_1[r];
                o_1[r]=o_0[r];
                o_0[r]=o;
            }
        pn(r,x,y);
        return;
    }
    pn(r,x,y);
    if(ql<=mid)
        fi(r<<1,x,mid,ql,qr,v);
    if(mid<qr)
        fi(r<<1|1,mid+1,y,ql,qr,v);
    pp(r);
}
int qu_s(int r,int x,int y,int ql,int qr)
{
    int mid=(x+y)>>1,k=0;
    if(ql<=x&&y<=qr)
        return s[r];
    pn(r,x,y);
    if(ql<=mid)
        k+=qu_s(r<<1,x,mid,ql,qr);
    if(mid<qr)
        k+=qu_s(r<<1|1,mid+1,y,ql,qr);
    return k;
}
co qu_o(int r,int x,int y,int ql,int qr)
{
    int mid=(x+y)>>1;
    bool p=0;
    co k,kk;
    if(ql<=x&&y<=qr)
        return o_1[r];
    pn(r,x,y);
    if(ql<=mid)
    {
        k=qu_o(r<<1,x,mid,ql,qr);
        p=1;
    }
    if(mid<qr)
    {
        kk=qu_o(r<<1|1,mid+1,y,ql,qr);
        if(k.y==kk.x-1)
        {
            k.s+=kk.s;
            k.y=kk.y;
        }
        else
            if(k.s<kk.s)
                k=kk;
    }
    return p?k:kk;
}
int main()
{
    int i,n,m,x,y,p;
    n=re();
    m=re();
    for(i=1;i<=n;i++)
        a[i]=re();
    bu(1,1,n);
    while(m--)
    {
        p=re();
        x=re();
        y=re();
        x++;
        y++;
        if(p>=0&&p<3)
            fi(1,1,n,x,y,p);
        else
            if(p==3)
                printf("%d\n",qu_s(1,1,n,x,y));
            else
                printf("%d\n",qu_o(1,1,n,x,y).s);
    }
    return 0;
}

by 夏色祭 @ 2018-03-13 21:54:02

您可以写个对拍啊


by Iowa_BattleShip @ 2018-03-14 09:06:36

@zykykyk 对拍拍了,但是调试调不出什么毛病,目前知道是取反的标记有问题,但看了半小时找不到哪里有问题……


by Iowa_BattleShip @ 2018-03-14 12:32:32

已AC,谢谢


|