hdu3911Black And White (线段树，段异或，段查寻)

There are a bunch of stones on the beach; Stone color is white or black. Little Sheep has a magic brush, she can change the color of a continuous stone, black to white, white to black. Little Sheep like black very much, so she want to know the longest period of consecutive black stones in a range [i, j].

Input

There are multiple cases, the first line of each case is an integer n(1<= n <= 10^5), followed by n integer 1 or 0(1 indicates black stone and 0 indicates white stone), then is an integer M(1<=M<=10^5) followed by M operations formatted as x i j(x = 0 or 1) , x=1 means change the color of stones in range[i,j], and x=0 means ask the longest period of consecutive black stones in range[i,j]

Output

When x=0 output a number means the longest length of black stones in range [i,j].

Sample Input

4

1 0 1 0

5

0 1 4

1 2 3

0 1 4

1 3 3

0 4 4

Sample Output

1

2

0

题目意思：有n个石头，分黑白两种，当x=1时，把在范围[i,j]的石头黑变白，白变黑；当x=1时，找出在范围[i,j]内的连续最长黑色石头，输出长度。

10

1 1 1 0 0 1 0 0 1 1

9

1 1 6

0 2 7

1 3 9

1 4 10

0 1 10

1 3 7

0 2 6

1 2 9

0 3 9

[2,3,1,3]

18

1 1 0 1 1 0 1 1 1 0 0 0 1 1 0 1 1 0

8

1 3 9

0 4 15

1 5 16

1 2 7

0 4 17

0 1 10

1 11 18

0 1 18

[2,5,3,3]

#include  
#include  
#include  
using namespace std;  
#define N 100100  
struct edg  
{  
    int len;//最左，右的长度  
    char c;//颜色  
};  
struct nn  
{  
    int wlen,blen,need;//分别代表当前段的最长连续白色，黑色和子节点是否须要更新（1更新，0不用）  
    struct edg LL,RR;//节点的最左边和最右边连续黑或白  
}tree[6*N];  
int max(int a,int b){return a>b a:b;}  
//-------------异或-------------  
void sepw(int k)  
{  
    int t;  
    t=tree[k].blen; tree[k].blen=tree[k].wlen; tree[k].wlen=t;  
    if(tree[k].LL.c=='w')tree[k].LL.c='b';else tree[k].LL.c='w';  
    if(tree[k].RR.c=='w')tree[k].RR.c='b';else tree[k].RR.c='w';  
}  
//----------根据子节点更新父节点k-----------  
void chang(int l,int r,int k)  
{  
    int m=(l+r)/2;  
    struct nn ltre=tree[k*2],rtre=tree[k*2+1];  
    //父节点的长度一定是从左右子节点的最长长度和跨越子节点的长度产生  
    tree[k].LL=ltre.LL; tree[k].RR=rtre.RR;  
    tree[k].blen=max(ltre.blen,rtre.blen);  
    tree[k].wlen=max(ltre.wlen,rtre.wlen);  
    if(ltre.RR.c=='w'&&rtre.LL.c=='w')//当中间连续为白色时  
    {  
        if(ltre.LL.c=='w'&





R)  
               len=max(tree[2*k].RR.len+R-m,len);  
        else if(L>m-tree[2*k].RR.len+1&&m+tree[k*2+1].LL.len<=R)  
                 len=max(m-L+1+tree[k*2+1].LL.len,len);  
        else  len=R-L+1;  
                        return len;  
}  
//------x=1时是异或段L~R，x=0时是查找段L~R内的最长黑色长度-----  
int len,x;  
void chang_color(int l,int r,int k,int L,int R)  
{  
    int m=(l+r)/2;  
    if(L<=l&&r<=R){  
        if(x==1){  
              if(tree[k].need) child_sepw(l,r,k);  
                tree[k].need=1; sepw(k);  
                if(l==r)tree[k].need=0;  
          }  
        else  len=max(tree[k].blen,len);  
                return ;  
    }  
    if(tree[k].need)  
    child_sepw(l,r,k);  
    if(R<=m)  
        chang_color(l,m,2*k,L,R);  
    else if(L>m)  
        chang_color(m+1,r,2*k+1,L,R);  
    else{  
        chang_color(l,m,2*k,L,R);  
        chang_color(m+1,r,2*k+1,L,R);  
            if(x==0) len=searchL_to_R(len,m,k,L,R);  
    }  
    chang(l,r,k); tree[k].need=0;  
}  
int main()  
{  
    int n,m,i,nc[N],L,R;//vectornc;  
    while(scanf("%d",&n)>0)  
    {  
        set_tree(1,n,1); //nc.clear();  
        for(i=1;i<=n;i++)  
         scanf("%d",&nc[i]); //{nc.push_back(c);}  
        for(i=1;i<=n;i++)  
        if(nc[i])  
        {  
            L=i; while(nc[i+1]&&i+1<=n) i++;  
            R=i; x=1; chang_color(1,n,1,L,R);  
        }  
        scanf("%d",&m);  
        while(m--)  
        {  
            scanf("%d%d%d",&x,&L,&R);  
            if(x==0)  
            {  
                len=0; chang_color(1,n,1,L,R);  
                printf("%d\n",len);  
            }  
            else chang_color(1,n,1,L,R);  
        }  
    }  
}