哪位大佬想挑战 调一下线段树(0分但感觉思路没问题)

P2572 [SCOI2010] 序列操作

Eternality @ 2022-10-26 09:58:01


#include<bits/stdc++.h>
using namespace std;

const int N=1e5+10;
int n,m,a[N];

struct T
{
    int l,r,sum;
    int l0,l1,r0,r1;
    int g,k1,k0;
    int tag1,tag2,tag3;
}t[N<<2];

T update(T &p,T ls,T rs)
{
    p.sum=ls.sum+rs.sum;
    p.l1=(ls.g==1 ? ls.r-ls.l+1+rs.l1 : ls.l1);
    p.l0=(ls.g==2 ? ls.r-ls.l+1+rs.l0 : ls.l0);
    p.r1=(rs.g==1 ? rs.r-rs.l+1+ls.r1 : rs.r1);
    p.r0=(rs.g==2 ? rs.r-rs.l+1+ls.l0 : rs.r0);
    if(p.sum==p.r-p.l+1)p.g=1;
    else if(p.sum==0)p.g=2;
    else p.g=0;
    p.k1=max(max(ls.k1,rs.k1),ls.r1+rs.l1);
    p.k0=max(max(ls.k0,rs.k0),ls.r0+rs.l0);
    return p;
}

void build(int p,int l,int r)
{
    t[p].l=l;
    t[p].r=r;
    if(l==r)
    {
        t[p].sum=a[l];
        if(a[l]==1)
        {
            t[p].l1=t[p].r1=1;
            t[p].l0=t[p].r0=0;
            t[p].g=1;
            t[p].k1=1;
            t[p].k0=0;
        }
        else
        {
            t[p].l0=t[p].r0=1;
            t[p].l1=t[p].r1=0;
            t[p].g=2;
            t[p].k1=0;
            t[p].k0=1;
        }
        return;
    }
    int mid=l+r>>1;
    build(p<<1,l,mid);
    build(p<<1|1,mid+1,r);
    update(t[p],t[p<<1],t[p<<1|1]);
}

void color(int p,int tag1,int tag2,int tag3)
{
    if((tag1&&!tag2&&!tag3)||(!tag1&&tag2&&tag3))
    {
        t[p].tag1=1;
        t[p].tag2=t[p].tag3=0;
        t[p].g=2;
        t[p].k0=t[p].r-t[p].l+1;
        t[p].k1=0;
        t[p].l0=t[p].r0=t[p].r-t[p].l+1;
        t[p].l1=t[p].r1=0;
        t[p].sum=0;
    }
    if((!tag1&&tag2&&!tag3)||(tag1&&!tag2&&tag3))
    {
        t[p].tag2=1;
        t[p].tag1=t[p].tag3=0;
        t[p].g=1;
        t[p].k1=t[p].r-t[p].l+1;
        t[p].k0=0;
        t[p].l1=t[p].r1=t[p].r-t[p].l+1;
        t[p].l0=t[p].r0=0;
        t[p].sum=t[p].r-t[p].l+1;
    }
    if(!tag1&&!tag2&&tag3)
    {
        t[p].tag3=1 xor t[p].tag3;
        if(t[p].g==2)t[p].g=1;
        if(t[p].g==1)t[p].g=2;
        int k0=t[p].k0,k1=t[p].k1;
        t[p].k1=k0;
        t[p].k0=k1;
        int l1=t[p].l1,l0=t[p].l0,r1=t[p].r1,r0=t[p].r0;
        t[p].l1=l0;
        t[p].l0=l1;
        t[p].r0=r1;
        t[p].r1=r0;
        t[p].sum=t[p].r-t[p].l+1-t[p].sum;
    }
}

void pushdown(int p)
{
    color(p<<1,t[p].tag1,t[p].tag2,t[p].tag3);
    color(p<<1|1,t[p].tag1,t[p].tag2,t[p].tag3);
    t[p].tag1=t[p].tag2=t[p].tag3=0;
}

void change(int p,int l,int r,int op)
{
    if(l<=t[p].l&&r>=t[p].r)
    {
        if(op==1)color(p,1,0,0);
        if(op==2)color(p,0,1,0);
        if(op==3)color(p,0,0,1);
        return;
    }
    pushdown(p);
    int mid=t[p].l+t[p].r>>1;
    if(l<=mid)change(p<<1,l,r,op);
    if(r>mid)change(p<<1|1,l,r,op);
    update(t[p],t[p<<1],t[p<<1|1]);
}

T ask(int p,int l,int r)
{
    if(l<=t[p].l&&r>=t[p].r)return t[p];
    pushdown(p);
    T ans;
    int mid=t[p].l+t[p].r>>1;
    if(l<=mid&&r>mid)return update(ans,ask(p<<1,l,r),ask(p<<1|1,l,r));
    if(r<=mid)return ask(p<<1,l,r);
    if(l>mid)return ask(p<<1|1,l,r);
}

int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    build(1,1,n);
    while(m--)
    {
        int op,l,r;
        scanf("%d%d%d",&op,&l,&r);
        op++,l++,r++;
        if(op==1||op==2||op==3)
        {
            change(1,l,r,op);
        }
        if(op==4||op==5)
        {
            if(op==4)cout<<ask(1,l,r).sum<<"\n";
            else cout<<ask(1,l,r).k1<<"\n";
        }
//      cout<<"T: ";
//      for(int i=1;i<=n;i++)cout<<a[i]<<" ";
//      cout<<endl;
    }
    return 0;
}

|