hdu3911Black And White (线段树，段异或，段查寻)
Problem DescriptionThere 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<stdio.h>
#include<iostream>
#include<vector>
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'&<re.LL.len==m-l+1)//最左边长度
tree[k].LL.len=ltre.LL.len+rtre.LL.len;
if(rtre.RR.c=='w'&&rtre.RR.len==r-m)//最右边长度
tree[k].RR.len=ltre.RR.len+rtre.RR.len;
tree[k].wlen=max(tree[k].wlen,ltre.RR.len+rtre.LL.len);
}
else if(ltre.RR.c=='b'&&rtre.LL.c=='b')//当中间连续为黑色时
{
if(ltre.LL.c=='b'&<re.LL.len==m-l+1)
tree[k].LL.len=ltre.LL.len+rtre.LL.len;
if(rtre.RR.c=='b'&&rtre.RR.len==r-m)
tree[k].RR.len=ltre.RR.len+rtre.RR.len;
tree[k].blen=max(tree[k].blen,ltre.RR.len+rtre.LL.len);
}
}
//--------初始时建树，全定白色-----------
void set_tree(int l,int r,int k)
{
tree[k].wlen=r-l+1; tree[k].blen=0;
tree[k].LL.c='w'; tree[k].LL.len=r-l+1;
tree[k].RR.c='w'; tree[k].RR.len=r-l+1;
tree[k].need=0;
if(l==r) return ;
int m=(l+r)/2;
set_tree(l,m,k*2);
set_tree(m+1,r,k*2+1);
}
//-------当父节点的need=1时，表明左右子节点要更新异或-------
void child_sepw(int l,int r,int k)
{
int m=(l+r)/2;
if(tree[2*k].need)//当左节点的need也为1时，左节点的左右子节点也须要异或
tree[2*k].need=0;//但须要异或两次则变回原来，那么就不须要异或，就把need变成0
else tree[k*2].need=1;//否则左节点的左右子节点须要异或
if(l==m)tree[k*2].need=0;
sepw(k*2); //异或左节点
if(tree[2*k+1].need)
tree[2*k+1].need=0;
else tree[k*2+1].need=1;
if(m+1==r)tree[k*2+1].need=0;
sepw(k*2+1);
}
//------查找L~R段的最长连续黑色是否跨越了节点K的左右子节点------
int searchL_to_R(int len,int m,int k,int L,int R)
{
if(tree[2*k].RR.c=='b'&&tree[2*k+1].LL.c=='b')
if(L<=m-tree[2*k].RR.len+1&&m+tree[k*2+1].LL.len<=R)
len=max(tree[2*k].RR.len+tree[k*2+1].LL.len,len);
else if(L<=m-tree[2*k].RR.len+1&&m+tree[k*2+1].LL.len>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;//vector<int>nc;
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);
}
}
}
补充：软件开发 , C++ ,
