求hack!对拍了七八组数据没出错,交上去除#11全WA!qaq

P2572 [SCOI2010] 序列操作

MCRS_lizi @ 2022-08-02 19:26:31

#include<bits/stdc++.h>
using namespace std;
const int N=100010;
int n,m,a[N],id[N],tot,blk;
struct sb
{
    int val,lazy1,lazy2,l,r;
    int len1,len2,len3;
    int len4,len5,len6;
}b[1001];
void pushdown(int p)
{
    for(int i=b[p].l;i<=b[p].r;i++)
    {
        if(b[p].lazy2)
        {
            a[i]=!a[i];
        }
        else if(b[p].lazy1!=-1)
        {
            a[i]=b[p].lazy1;
        }
    }
    b[p].lazy1=-1;
    b[p].lazy2=0;
}
void clear(int p)
{
    int sum[2]={0,0};
    for(int i=b[p].l;i<=b[p].r;i++)
    {
        sum[a[i]]++;
        sum[!a[i]]=0;
        b[p].len2=max(sum[1],b[p].len2);
        b[p].len5=max(sum[0],b[p].len5);
    }
    int num=1;
    for(int i=b[p].l+1;i<=b[p].r;i++)
    {
        if(a[i]!=a[i-1])
        {
            if(a[i-1])
            {
                b[p].len1=num;
                b[p].len4=0;
            }
            else
            {
                b[p].len4=num;
                b[p].len1=0;
            }
            break;
        }
        num++;
    }
    if(num==1+b[p].r-b[p].l)
    {
        if(a[b[p].l])
        {
            b[p].len1=num;
            b[p].len4=0;
        }
        else
        {
            b[p].len4=num;
            b[p].len1=0;
        }
    }
    num=1;
    for(int i=b[p].r-1;i>=b[p].l;i--)
    {
        if(a[i]!=a[i+1])
        {
            if(a[i+1])
            {
                b[p].len3=num;
                b[p].len6=0;
            }
            else
            {
                b[p].len3=num;
                b[p].len6=0;
            }
            break;
        }
        num++;
    }
    if(num==1+b[p].r-b[p].l)
    {
        if(a[b[p].l])
        {
            b[p].len3=num;
            b[p].len6=0;
        }
        else
        {
            b[p].len6=num;
            b[p].len3=0;
        }
    }
}
void update(int l,int r,int q)
{
    if(id[l]==id[r])
    {
        pushdown(id[l]);
        for(int i=l;i<=r;i++)
        {
            b[id[l]].val+=q-a[i];
            a[i]=q;
        }
        clear(id[l]);
    }
    else
    {
        pushdown(id[l]);
        pushdown(id[r]);
        for(int i=l;i<=b[id[l]].r;i++)
        {
            b[id[l]].val+=q-a[i];
            a[i]=q;
        }
        for(int i=b[id[r]].l;i<=r;i++)
        {
            b[id[r]].val+=q-a[i];
            a[i]=q;
        }
        for(int i=id[l]+1;i<id[r];i++)
        {
            b[i].val=(b[i].r-b[i].l+1)*q;
            b[i].lazy1=q;
            b[i].lazy2=0;
            if(q)
            {
                b[i].len1=b[i].len2=b[i].len3=b[i].r-b[i].l+1;
                b[i].len4=b[i].len5=b[i].len6=0;
            }
            else
            {
                b[i].len1=b[i].len2=b[i].len3=0;
                b[i].len4=b[i].len5=b[i].len6=b[i].r-b[i].l+1;
            }
        }
        clear(id[l]);
        clear(id[r]);
    }
}
void change(int l,int r)
{
    if(id[l]==id[r])
    {
        pushdown(id[l]);
        for(int i=l;i<=r;i++)
        {
            if(a[i])
            {
                b[id[l]].val--;
            }
            else
            {
                b[id[l]].val++;
            }
            a[i]=!a[i];
        }
        clear(id[l]);
    }
    else
    {
        pushdown(id[l]);
        pushdown(id[r]);
        for(int i=l;i<=b[id[l]].r;i++)
        {
            if(a[i])
            {
                b[id[l]].val--;
            }
            else
            {
                b[id[l]].val++;
            }
            a[i]=!a[i];
        }
        for(int i=b[id[r]].l;i<=r;i++)
        {
            if(a[i])
            {
                b[id[r]].val--;
            }
            else
            {
                b[id[r]].val++;
            }
            a[i]=!a[i];
        }
        clear(id[l]);
        clear(id[r]);
        for(int i=id[l]+1;i<id[r];i++)
        {
            if(b[i].lazy1!=-1)
            {
                b[i].lazy1=!b[i].lazy1;
            }
            else
            {
                b[i].lazy2=!b[i].lazy2;
            }
            b[i].val=(b[i].r-b[i].l+1)-b[i].val;
            swap(b[i].len1,b[i].len4);
            swap(b[i].len2,b[i].len5);
            swap(b[i].len3,b[i].len6);
        }
    }
}
int query1(int l,int r)
{
    int res=0;
    if(id[l]==id[r])
    {
        pushdown(id[l]);
        for(int i=l;i<=r;i++)
        {
            res+=a[i];
        }
    }
    else
    {
        pushdown(id[l]);
        pushdown(id[r]);
        for(int i=l;i<=b[id[l]].r;i++)
        {
            res+=a[i];;
        }
        for(int i=b[id[r]].l;i<=r;i++)
        {
            res+=a[i];
        }
        for(int i=id[l]+1;i<id[r];i++)
        {
            res+=b[i].val;
        }
    }
    return res;
}
int query2(int l,int r)
{
    int res=0,cnt=0;
    if(id[l]==id[r])
    {
        pushdown(id[l]);
        for(int i=l;i<=r;i++)
        {
            if(a[i])
            {
                cnt++;
            }
            else
            {
                cnt=0;
            }
            res=max(cnt,res);
        }
    }
    else
    {
        pushdown(id[l]);
        pushdown(id[r]);
        for(int i=l;i<=b[id[l]].r;i++)
        {
            if(a[i])
            {
                cnt++;
            }
            else
            {
                cnt=0;
            }
            res=max(cnt,res);
        }
        for(int i=id[l]+1;i<id[r];i++)
        {
            cnt+=b[i].len1;
            res=max(res,max(b[i].len2,cnt));
            if(b[i].len1!=b[i].len3)
            {
                cnt=b[i].len3;
            }
        }
        for(int i=b[id[r]].l;i<=r;i++)
        {
            if(a[i])
            {
                cnt++;
            }
            else
            {
                cnt=0;
            }
            res=max(cnt,res);
        }
    }
    return res;
}
int main()
{
    std::ios::sync_with_stdio(false);
    cin>>n>>m;
    blk=sqrt(n);
    int sum[2]={0,0},flag[2]={0,0};
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        if(flag[a[i]]==0&&flag[!a[i]]==1)
        {
            flag[!a[i]]==0;
            if(a[i])
            {
                b[tot].len1=0;
                b[tot].len4=sum[0];
            }
            else
            {
                b[tot].len4=0;
                b[tot].len1=sum[1];
            }
        }
        sum[a[i]]++;
        sum[!a[i]]=0;
        if(i%blk==0)
        {
            b[tot].r=i;
            b[tot].len3=sum[1];
            b[tot].len6=sum[0];
        }
        else if(i%blk==1)
        {
            b[++tot].l=i;
            flag[a[i]]=1;
            flag[!a[i]]=0;
        }
        b[tot].len2=max(b[tot].len2,sum[1]);
        b[tot].len5=max(b[tot].len5,sum[0]);
        id[i]=tot;
        b[tot].val+=a[i];
        b[tot].lazy1=-1;
    }
    while(m--)
    {
        int q,l,r;
        cin>>q>>l>>r;
        l++,r++;
        if(q<=1)
        {
            update(l,r,q);
        }
        else if(q==2)
        {
            change(l,r);
        }
        else if(q==3)
        {
            printf("%d\n",query1(l,r));
        }
        else
        {
            printf("%d\n",query2(l,r));
        }
//      for(int i=1;i<=tot;i++)
//      {
//          pushdown(i);
//      }
//      for(int i=1;i<=n;i++)
//      {
//          cout<<a[i]<<" ";
//      }
//      cout<<endl;
    }
    return 0;
}

RT,本蒟蒻悬赏一个关注qwq


by MCRS_lizi @ 2022-08-02 19:27:21

懒得写线段树,写的分块QAQ


by MCRS_lizi @ 2022-08-02 19:36:05

至少现在对拍出错误数据了


by MCRS_lizi @ 2022-08-02 19:45:39

发现了一个错误,但还是只有10pts qaq


|