hdu 3911 Black And White（线段树）

这道题很麻烦，比较烦的是题目其实没什么含金量，就是延迟标记加区间合并。

昨天晚上一点半被蚊子咬得睡不着，就起来做这个题。从一点半做到快三点，提交wa。当时我就去睡了，早上来继续debug。

做一个小修改之后，试探性地提交了一次，无悬念wa。后来又debug了半天，终于找到一个藏得很深的错误，提交后796msAC。

题目麻烦的是我们求的是最长的1的连续序列，但是因为题目中的操作是一个异或操作，所以还得记录0的信息。在更新节点信息的时候，要将1转环为0，0转换为1。别的地方就是线段树的两种基本操作了。

#include<stdio.h>
#include<string.h>
#define N 100005
struct node
{
    int x,y;
    int flag;
    int ll,lr;
    int max1,max0;
    int lflag,rflag;
}a[N*3];
int b[N];
int Max(int x,int y)
{
    if(x>y)
        return x;
    else
        return y;
}
int Min(int x,int y)
{
    if(x<y)
        return x;
    else 
        return y;
}
void CreatTree(int t,int x,int y)
{
    a[t].x=x;
    a[t].y=y;
    a[t].flag=0;
    a[t].ll=a[t].lr=y-x+1;
    a[t].max1=0;
    a[t].max0=y-x+1;
    a[t].lflag=a[t].rflag=0;
    //printf("%d %d %d %d\n",a[t].x,a[t].y,a[t].max0,a[t].max1);
    if(x==y)
        return ;
    int temp=t*2;
    int mid=(x+y)/2;
    CreatTree(temp,x,mid);
    CreatTree(temp+1,mid+1,y);
    //printf("%d %d %d %d\n",a[t].x,a[t].y,a[t].max0,a[t].max1);
    return ;
}
void ChangeTree(int t)
{
    int temp;
    temp=a[t].max0;
    a[t].max0=a[t].max1;
    a[t].max1=temp;
    a[t].lflag=(a[t].lflag+1)%2;
    a[t].rflag=(a[t].rflag+1)%2;
    a[t].flag=(a[t].flag+1)%2;
    return ;
}
void InsertTree(int t,int x,int y)
{
    if(a[t].x==x&&a[t].y==y)
    {
        ChangeTree(t);
        //printf("%d %d %d %d\n",a[t].x,a[t].y,a[t].max0,a[t].max1);
        return ;
    }
    int temp=t*2;
    int mid=(a[t].x+a[t].y)/2;
    if(a[t].flag)
    {
        ChangeTree(temp);
        ChangeTree(temp+1);
        a[t].flag=0;
    }
    if(y<=mid)
        InsertTree(temp,x,y);
    else if(x>mid)
        InsertTree(temp+1,x,y);
    else
    {
        InsertTree(temp,x,mid);
        InsertTree(temp+1,mid+1,y);
    }
    int tt=0;
    if(a[temp].rflag==a[temp+1].lflag)
        tt=a[temp].lr+a[temp+1].ll;
    if(a[temp].rflag==0&&tt)
        a[t].max0=Max(tt,Max(a[temp].max0,a[temp+1].max0));
    else
        a[t].max0=Max(a[temp].max0,a[temp+1].max0);
    if(a[temp].rflag==1&&tt)
        a[t].max1=Max(tt,Max(a[temp].max1,a[temp+1].max1));
    else
        a[t].max1=Max(a[temp].max1,a[temp+1].max1);
    if(a[temp].ll==a[temp].y-a[temp].x+1&&tt)
        a[t].ll=tt;
    else
        a[t].ll=a[temp].ll;
    a[t].lflag=a[temp].lflag;
    if(a[temp+1].lr==a[temp+1].y-a[temp+1].x+1&&tt)
        a[t].lr=tt;
    else
        a[t].lr=a[temp+1].lr;
    a[t].rflag=a[temp+1].rflag;
    //printf("%d %d %d %d\n",a[t].x,a[t].y,a[t].max0,a[t].max1);
    return ;
}
int FindTree(int t,int x,int y)
{
    if(a[t].x==x&&a[t].y==y)
        return a[t].max1;
    int temp=t*2;
    int mid=(a[t].x+a[t].y)/2;
    if(a[t].flag)
    {
        ChangeTree(temp);
        ChangeTree(temp+1);
        a[t].flag=0;
    }
    if(y<=mid)
        return FindTree(temp,x,y);
    else if(x>mid)
        return FindTree(temp+1,x,y);
    else
    {
        int tt,lt,rt;
        if(a[temp].rflag==a[temp+1].lflag&&a[temp].rflag)
        {
            lt=Min(a[temp].lr,mid-x+1);
            rt=Min(a[temp+1].ll,y-mid);
            tt=lt+rt;
            return Max(tt,Max(FindTree(temp,x,mid),FindTree(temp+1,mid+1,y)));
        }
        else
            return Max(FindTree(temp,x,mid),FindTree(temp+1,mid+1,y));
    }
    return 0;
}
int main()
{
    int n;
    while(scanf("%d",&n)!=EOF)
    {
        int i;
        CreatTree(1,1,n);
        for(i=1;i<=n;i++)
        {
            scanf("%d",&b[i]);
            if(b[i])
                InsertTree(1,i,i);
        }    
        int m;
        scanf("%d",&m);
        while(m--)
        {
            int x,y,z;
            scanf("%d%d%d",&x,&y,&z);
            if(x==0)
                printf("%d\n",FindTree(1,y,z));
            else
                InsertTree(1,y,z);
        }
    }
    return 0;
}

补充：软件开发 , C++ ,