hdu 3911 Black And White 线段树

代码写得比较乱。

区间最长连续黑色：maxb

区间最长连续白色：maxw

区间左端点颜色：lcolor

区间右端点颜色：rcolor

左端点起最长连续数：lmax

右端点起最长连续数：rmax

标记区间是否被更改过：flag

#include<iostream>

using namespace std;

struct tree
{
    int left;
    int right;
    int maxb,maxw;
    int lcolor,rcolor;
    int lmax,rmax;
    int flag;
}t[400000];

inline int max(int a,int b)
{
    return a>b? a:b;
}
inline int min(int a,int b)
{
    return a>b? b:a;
}

int key[100005];

void create(int l,int r,int now);
void add_node(int now);
void update_node(int now);
void update_tree(int l,int r,int now);
void change_node(int now);
int query(int l,int r,int now);

int main()
{
    int n,m,x,l,r,ans;

    while(scanf("%d",&n)!=EOF)
    {
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&key[i]);
        }

        create(1,n,1);
        add_node(1);

        cin>>m;
        while(m--)
        {
            scanf("%d%d%d",&x,&l,&r);

            if(x==0)
            {
                ans=query(l,r,1);
                printf("%d\n",ans);
            }
            else
                update_tree(l,r,1);
        }
    }
    return 0;
}

void create(int l,int r,int now)
{
    t[now].left=l;
    t[now].right=r;

    t[now].lmax=0;
    t[now].rmax=0;

    t[now].maxb=0;
    t[now].maxw=0;

    t[now].rcolor=0;
    t[now].lcolor=0;

    t[now].flag=0;

    if(l<r)
    {
        int mid=(r+l)>>1;

        create(l,mid,now<<1);
        create(mid+1,r,(now<<1)+1);        
    }

    return;
}

void add_node(int now)
{
    if(t[now].left==t[now].right)
    {
        t[now].lcolor=t[now].rcolor=key[t[now].left];

        t[now].lmax=t[now].rmax=1;

        t[now].maxb=key[t[now].left];
        t[now].maxw=1-key[t[now].left];

        t[now].flag=0;

        return ;
    }

    add_node(now<<1);
    add_node( (now<<1)+1 );
    update_node(now);
    return ;
}

void update_node(int now)
{
    int left=now<<1,right=(now<<1)+1;

    t[now].lcolor=t[left].lcolor;
    t[now].rcolor=t[right].rcolor;

    if(t[left].lmax==t[left].right-t[left].left+1 && t[left].rcolor==t[right].lcolor)
        t[now].lmax=t[left].lmax+t[right].lmax;
    else
        t[now].lmax=t[left].lmax;

    if(t[right].rmax==t[right].right-t[right].left+1 && t[right].lcolor==t[left].rcolor)
        t[now].rmax=t[right].rmax+t[left].rmax;
    else
        t[now].rmax=t[right].rmax;

    t[now].maxb=max(t[right].maxb,t[left].maxb);
    t[now].maxw=max(t[right].maxw,t[left].maxw);

    if(t[left].rcolor==t[right].lcolor)
    {
        if(t[left].rcolor==1)
            t[now].maxb=max(t[now].maxb,t[left].rmax+t[right].lmax);
        else if(t[left].rcolor==0)
            t[now].maxw=max(t[now].maxw,t[left].rmax+t[right].lmax);
    }
}

void update_tree(int l,int r,int now)
{
    if(t[now].left==l && t[now].right==r)
    {
        change_node(now);
        return ;
    }

    if(t[now].flag==1)
    {
        change_node(now<<1);
        change_node( (now<<1) +1);

        t[now].flag=0;
    }

    int mid=(t[now].left+t[now].right)>>1;

    if(r<=mid)
        update_tree(l,r,now<<1);
    else if(l>mid)
        update_tree(l,r,(now<<1)+1);
    else
    {
        update_tree(l,mid,now<<1);
        update_tree(mid+1,r,(now<<1)+1);
    }
    update_node(now);
}

void change_node(int now)
{
    t[now].lcolor=t[now].lcolor^1;
    t[now].rcolor=t[now].rcolor^1;

    t[now].maxb=t[now].maxb^t[now].maxw;
    t[now].maxw=t[now].maxb^t[now].maxw;
    t[now].maxb=t[now].maxb^t[now].maxw;

    t[now].flag=t[now].flag^1;
}

int query(int l,int r,int now)
{
    if(t[now].left==l && t[now].right==r)
        return t[now].maxb;

    if(t[now].flag==1)
    {
        change_node(now<<1);
        change_node( (now<<1)+1 );
        t[now].flag=0;
    }

    int mid=(t[now].left+t[now].right)>>1;
//    int left=now<<1,right=(now<<1)+1;
    int t1=0,t2=0,t3=0,t4=0,t5=0;

    if(r<=mid)
        t1=query(l,r,now<<1);
    else if(l>mid)
        t2=query(l,r,(now<<1)+1);
    else
    {
        t3=query(l,mid,now<<1);
        t4=query(mid+1,r,(now<<1)+1);

        if(t[now<<1].rcolor==1 && t[ (now<<1)+1 ].lcolor==1)
            t5=min(mid-l+1,t[now<<1].rmax)+min(r-mid,t[ (now<<1)+1].lmax);
    }
    update_node(now);
    return max( max( max(t1,t2),max(t3,t4) ) , t5);
}