HDU 3911 Black And White （線段樹區(qū)間更新）

題目鏈接：http://acm.hdu.edu.cn/showproblem.php?pid=3911

題面：

Black And White Time Limit: 9000/3000 MS (Java/Others)????Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 4358????Accepted Submission(s): 1271


Problem Description 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 ?
Source 2011 Multi-University Training Contest 8 - Host by HUST

題目大意：

??? 初始給定一01序列，兩種操作，1 a b，取反a到b間的元素，0 a b，問a b區(qū)間內(nèi)最長的連續(xù)1的長度。

解題：

??? 第一顆區(qū)間更新的線段樹，來得有點晚啊，借鑒、理解也算是寫出來了。題意看似簡單，合并操作比較復(fù)雜。需要維護5個值。maxw,maxb,le,ri,lazy。

??? maxw/maxb，該區(qū)間的最長連續(xù)0/1長度，取反時直接交換兩值。

??? le/ri，該區(qū)間的左右連續(xù)塊長度，用于合并。

??? lazy該區(qū)間是否需要繼續(xù)向下更新。

代碼：

#include 
#include 
#include 
#define siz 100010
//左右子樹編號
#define ls i<<1
#define rs (i<<1)|1
using namespace std;
//左右邊界，該區(qū)間最多連續(xù)黑塊數(shù)，白塊數(shù)，因為反轉(zhuǎn)區(qū)間需要
//區(qū)間左邊界連續(xù)塊數(shù)，右邊解連續(xù)塊數(shù)，正表黑，負表白，用于區(qū)間合并
//lazy標記如果為1，代表更新到該區(qū)間，其下區(qū)間尚未更新
struct SEGTree
{
	int l,r,maxb,maxw,le,ri,lazy;
}STree[siz<<2];
int a[siz];
//取大
int max(int x,int y)
{
	return x>y?x:y;
}
//取小
int min(int a,int b)
{
  return a0&&STree[rs].le>0)
   {
	   tmp=STree[ls].ri+STree[rs].le;
	   if(tmp>maxb)
		   maxb=tmp;
   }
   //更新
   STree[i].maxb=maxb;
   //白塊更新同上
   int maxw=max(STree[ls].maxw,STree[rs].maxw);
   if(STree[ls].ri<0&&STree[rs].le<0)
   {
	   tmp=STree[ls].ri+STree[rs].le;
	   tmp=-tmp;
	   if(tmp>maxw)
		   maxw=tmp;
   }
   STree[i].maxw=maxw;
   //區(qū)間左端最長連續(xù)塊數(shù)le，如果左子區(qū)單色，且能與右子區(qū)相連，更新le
   if(abs(STree[ls].le)==(STree[ls].r-STree[ls].l+1)&&(STree[ls].ri*STree[rs].le>0))
	   STree[i].le=STree[ls].le+STree[rs].le;
   //否則直接取左子區(qū)le
   else STree[i].le=STree[ls].le;
   //更新ri，同上
   if(abs(STree[rs].ri)==(STree[rs].r-STree[rs].l+1)&&(STree[ls].ri*STree[rs].le>0))
	   STree[i].ri=STree[ls].ri+STree[rs].ri;
   else STree[i].ri=STree[rs].ri;
}
//向下更新
void push_down(int i)
{
	//該區(qū)間的懶標記清零
	STree[i].lazy=0;
	//更新左右子區(qū)間
	swap(STree[ls].maxw,STree[ls].maxb);
	STree[ls].le=-STree[ls].le;
	STree[ls].ri=-STree[ls].ri;
	STree[ls].lazy=!STree[ls].lazy;
	swap(STree[rs].maxw,STree[rs].maxb);
	STree[rs].le=-STree[rs].le;
	STree[rs].ri=-STree[rs].ri;
	STree[rs].lazy=!STree[rs].lazy;
}
//建樹
void build(int i,int l,int r)
{
	STree[i].l=l;
	STree[i].r=r;
	STree[i].lazy=0;
	//葉子節(jié)點
	if(l==r)
	{
		//如果是黑塊
	   if(a[l])
	   {
		   STree[i].maxb=1;
		   STree[i].maxw=0;
		   STree[i].le=1;
		   STree[i].ri=1;
	   }
	   //白塊
	   else
	   {
		   STree[i].maxw=1;
		   STree[i].maxb=0;
		   STree[i].le=-1;
		   STree[i].ri=-1;
	   }
	   return;
	}
	//向下遞歸
	int mid=(l+r)>>1;
	build(i<<1,l,mid);
	build((i<<1)|1,mid+1,r);
	//向上更新
	push_up(i);
}
void update(int i,int l,int r)
{
	//如果剛好區(qū)間吻合
	if(STree[i].l==l&&STree[i].r==r)
	{
		//黑白塊交換
		swap(STree[i].maxw,STree[i].maxb);
		STree[i].le=-STree[i].le;
		STree[i].ri=-STree[i].ri;
		//lazy取反
		STree[i].lazy=!STree[i].lazy;
		return;
	}
	//如果沒有剛好吻合，要訪問的區(qū)間為當前區(qū)間子區(qū)間，
	//且該區(qū)間還有懶標記未下放，則向下更新，并向下訪問
	if(STree[i].lazy)
		push_down(i);
	int mid=(STree[i].l+STree[i].r)>>1;
	if(r<=mid)
		update(ls,l,r);
	else if(l>mid)
		update(rs,l,r);
	else
	{
		update(ls,l,mid);
		update(rs,mid+1,r);
	}
	//更新之后，向上更新
	push_up(i);
}
int query(int i,int l,int r)
{
	//如果剛好吻合，則返回區(qū)間最大連續(xù)黑塊
	if(l==STree[i].l&&r==STree[i].r)
	  return STree[i].maxb;
	int mid=(STree[i].l+STree[i].r)>>1;
	//不能完全符合，且該區(qū)間尚有懶標記，下放懶標記
	if(STree[i].lazy)
		push_down(i);    
	//向下查詢
	if(r<=mid)
	  return query(ls,l,r);
	else if(l>mid)
	  return query(rs,l,r);
	else
	{
		int res,tmp;
		//取左右最值，合并的最值
		res=max(query(ls,l,mid),query(rs,mid+1,r));
		//此處不僅僅合并左右區(qū)間最值，還需限制左右邊界不能超出查詢區(qū)間以mid為中心的左右邊界
        tmp=min(mid-l+1,STree[ls].ri)+min(r-mid,STree[rs].le);
		if(tmp>res)
		  res=tmp;
		return res;
	}
}
int main()
{
    int n,q,oper,fm,to;
	while(~scanf("%d",&n))
	{
	  //讀入
	  for(int i=1;i<=n;i++)
	    scanf("%d",&a[i]);
	  //建樹
      build(1,1,n);
	  scanf("%d",&q);
	  for(int i=1;i<=q;i++)
	  {
		  scanf("%d",&oper);
          scanf("%d%d",&fm,&to);
		  if(oper)
			update(1,fm,to);
		  else
          {
              int ans=query(1,fm,to);
              printf("%dn",ans);
          }
	  }
	}
	return 0;
}