hdu 3911 black and white 线段树区间合并

本文主要是介绍hdu 3911 black and white 线段树区间合并，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

线段树题目的类型大致可以分为四种：单点更新、成段增减或更新、区间合并和扫描线

成段更新和区间合并都需要用到Lazy思想。

扫描线就是求矩形面积和周长的题目，需要用到离散化。

本篇讲解区间合并，区间合并肯定是从子节点向上才能用着合并，这类题目都是求最长连续区间的，主要在PushUp的时候需要对左右儿子的区间进行合并。

这里就直接拿题目说事，所有的解释全部在代码的注释里。

1 0 1 0

0 1 4

1 2 3

0 1 4

1 3 3

0 4 4

首先输入N，表示序列长度，接下来一行输入4个数，只有0和1；接着输入一个值m表示m个操作，每个操作输入三个数a,b,c，a只有0和1，0表示查询[b,c]区间最长的连续1的长度，1表示将区间[b,c]内的0,1翻转。

[html]  view plain copy  
 print ? 
 struct Node  
 {  
     int l,r;  
     int lsum0,lsum1,rsum0,rsum1,msum0,msum1;//lsum0,rsum0,msum0分别表示一条线段从左边数最长连续的0个数，从右边最长连续0的个数，这条线段最长连续0的个数，同理lsum1,rsum1,msum1就不解释了  
     int ck;//=0时表示不用翻转，=1时才翻转  
     int mid()  
     {  
         return (l+r)>>1;  
     }  
 } tree[N << 2];  
   
 int a[N];  
   
 void PushUp(int rt)//合并操作  
 {  
     int ll = tree[rt<<1].r - tree[rt<<1].l + 1;//求左子树的线段长度  
     int rl = tree[rt<<1|1].r - tree[rt<<1|1].l + 1;//求右子树的线段长度  
   
     tree[rt].lsum1 = tree[rt<<1].lsum1;//首先求rt节点左边连续1个数，首先毋庸至于等于左子树的左边连续1的个数  
     if(tree[rt<<1].lsum1 == ll) tree[rt].lsum1 += tree[rt<<1|1].lsum1;//如果左子树连续1的个数刚好等于左子树的长度，那么rt节点的左边连续1的个数还需要加上右子树左边连续1的个数。下面的类似，这就是合并过程  
   
     tree[rt].rsum1 = tree[rt<<1|1].rsum1;  
     if(tree[rt<<1|1].rsum1 == rl) tree[rt].rsum1 += tree[rt<<1].rsum1;  
 //介绍如何求根节点最长连续1的个数，它是左子树最长连续1个数、右子树最长连续1个数和（左子树右边连续1的个数+右子树左边连续1的个数）三者的最大值  
     tree[rt].msum1 = max((tree[rt<<1].rsum1 + tree[rt<<1|1].lsum1) , max(tree[rt<<1].msum1,tree[rt<<1|1].msum1));  
   
     tree[rt].lsum0 = tree[rt<<1].lsum0;  
     if(tree[rt<<1].lsum0 == ll) tree[rt].lsum0 += tree[rt<<1|1].lsum0;  
   
     tree[rt].rsum0 = tree[rt<<1|1].rsum0;  
     if(tree[rt<<1|1].rsum0 == rl) tree[rt].rsum0 += tree[rt<<1].rsum0;  
   
     tree[rt].msum0 = max( (tree[rt<<1].rsum0 + tree[rt<<1|1].lsum0) , max(tree[rt<<1].msum0,tree[rt<<1|1].msum0));  
 }  
   
   
 void PushDown(int rt)//从父节点向下更新，这里其实是Lazy  
 {  
     if(tree[rt].ck == 1)//如果ck=1表示这里需要翻转，翻转其实就是把左右子树的0,1的lsum，rsum,msum交换  
     {  
         tree[rt<<1].ck ^= 1;//这里如果有疑问为什么是异或操作的话，因为现在左子树的父亲节点rt的线段所有0,1需要交换，那么他的左子树的线段是从父亲节点的线段继承下来的，当然也需要交换（下面的就是交换代码），那么左子树的左右子树也需要交换，如果原来tree[rt<<1].ck=1则说明原来左子树的左右子树就需要交换，现在还需要交换，交换两次等于没有交换，那么异或之后就不用交换了。所以刚好，需要用异或操作。  
         tree[rt<<1|1].ck ^= 1;  
         tree[rt].ck = 0;//恢复rt的ck值为0，它的左右子树已经交换了  
         swap(tree[rt<<1].lsum1,tree[rt<<1].lsum0);  
         swap(tree[rt<<1].rsum1,tree[rt<<1].rsum0);  
         swap(tree[rt<<1].msum1,tree[rt<<1].msum0);  
   
         swap(tree[rt<<1|1].lsum1,tree[rt<<1|1].lsum0);  
         swap(tree[rt<<1|1].rsum1,tree[rt<<1|1].rsum0);  
         swap(tree[rt<<1|1].msum1,tree[rt<<1|1].msum0);  
     }  
 }  
   
 void build(int l,int r,int rt)//建树  
 {  
     tree[rt].l = l;  
     tree[rt].r = r;  
     tree[rt].ck = 0;//初始化都不需要交换  
     if(l == r)//到每个叶子节点，付给初始值，这里不用解释  
     {  
         if(a[l] == 1)//black  
         {  
             tree[rt].lsum1 = tree[rt].rsum1 = tree[rt].msum1 = 1;  
             tree[rt].lsum0 = tree[rt].rsum0 = tree[rt].msum0 = 0;  
         }  
         else  
         {  
             tree[rt].lsum1 = tree[rt].rsum1 = tree[rt].msum1 = 0;  
             tree[rt].lsum0 = tree[rt].rsum0 = tree[rt].msum0 = 1;  
         }  
         return;  
     }  
     int m = (l + r) >> 1;  
     build(l,m,rt<<1);  
     build(m+1,r,rt<<1|1);  
     PushUp(rt);//从叶子节点递归向上合并  
 }  
   
 void update(int l,int r,int rt)  
 {  
     if(tree[rt].l == l && tree[rt].r == r)//刚好是需要更新区间[l,r]，直接更新  
     {  
         tree[rt].ck ^= 1;  
         swap(tree[rt].lsum1,tree[rt].lsum0);//更新rt节点线段的值  
         swap(tree[rt].rsum1,tree[rt].rsum0);  
         swap(tree[rt].msum1,tree[rt].msum0);  
         return;//这里直接return，根据Lazy的思想，只有在用到子树的时候才去更新子树  
     }  
     PushDown(rt);//这里需要用到子树的值，需要去更新  
     int m = tree[rt].mid();  
     if(r <= m) update(l,r,rt<<1);  
     else if(l > m) update(l,r,rt<<1|1);  
     else  
     {  
         update(l,m,rt<<1);  
         update(m+1,r,rt<<1|1);  
     }  
     PushUp(rt);//同样需要向上合并  
 }  
   
 int query(int l,int r,int rt)//查询  
 {  
     if(tree[rt].l == l && tree[rt].r == r)//刚好到查询区间  
     {  
         return tree[rt].msum1;  
     }  
     PushDown(rt);//同样是Lazy  
     int m = tree[rt].mid();  
     if(r <= m)  return query(l,r,rt<<1);//在左子树  
     else if(l>m) return query(l,r,rt<<1|1);//在右子树  
     else  
     {//这种情况就需要判断，左子树、右子树和中间三者的最大值  
         int lr = query(l,m,rt<<1);//左子树  
         int rr = query(m+1,r,rt<<1|1);//右子树  
         //中间  
         int a = tree[rt<<1].rsum1;//左子树右边最长连续1，注意它的个数不应该大于区间[l,tree[rt<<1].r]的个数  
         if(a > tree[rt<<1].r - l + 1) a = tree[rt<<1].r-l+1;  
   
         int b = tree[rt<<1|1].lsum1;//右子树左边最长连续1，注意它的个数不应该大于区间[tree[rt<<1|1].l,r]的个数  
         if(b > r - tree[rt<<1|1].l + 1) b = r - tree[rt<<1|1].l + 1;  
         return max(max(lr,rr),a+b);//最后取左子树、右子树和中间三者的最大值  
     }  
 }  
   
 int main()  
 {  
     int n,m,t,b,c;  
     while(scanf("%d",&n) != EOF)  
     {  
         for(int i = 1; i <= n ; i ++) scanf("%d",&a[i]);  
         build(1,n,1);  
         scanf("%d",&m);  
         while(m--)  
         {  
             scanf("%d %d %d",&t,&b,&c);  
             if(t==0)  
             {  
                 printf("%d\n",query(b,c,1));  
             }  
             else  
             {  
                 update(b,c,1);  
             }  
         }  
     }  
     return 0;  
 }  