区间合并是一类问题的统称，种类很多，但在这篇博客中只需实现以下操作即可：
有一个01串，你有三种操作：

• 1.将[a, b]中的所有数字改成0
• 2.将[a, b]中的所有数字改成1
• 3.询问[a, b]中最长连续的1的长度是多少

前两种操作其实可以算作一个操作，重点在于如何高效地解决第三种操作。
虽说平衡树也可以解决这类问题，但是这里我们使用线段树来解决。

这是一个经典的老套路

线段树维护四个值（可以缩成三个，使用第四个是为了加强程序的可读性），分别是：

• lsum记录该区间左端点开始的最长连续的值为1区间
• rsum记录该区间右端点开始的最长连续的值为1区间
• sum记录该区间内最长连续的值为1的区间
• color形象解释就是记录区间的“颜色”，具体操作是当这个区间全部是1时color置1，全部为0时color置0，否则置-1。在pushup()的时候会用到。

接下来来讲讲具体的操作

首先是重中之重$pushup()$

这里博主有点懒，就不画图了，相信听了讲解自己脑补一下也是能搞懂的（听起来真的很简单~~）。
开始假设当前节点为$this$，其左儿子为$lc$，右儿子为$rc$，且$lc$，$rc$中四个值均准确无误，接下来要对$this$节点做$pushup()$操作。
分步骤讨论：

• 1、计算$lsum$
  脑补一下，当$lc$的$color$为1时（也就是说左儿子结点全部由1组成），那么$lsum$就是$lc$的$lsum$（实际上$lsum$，$rsum$，$sum$的值都是左儿子结点的区间长度，换一下也没有什么大的差别）加上$rc$的$lsum$。否则直接赋值为$lc->lsum$。
• 2、计算$rsum$
  与计算$lsum$的方法类似,当$rc$的$color$为1时，那么$rsum$就是$rc$的$rsum$加上$lc$的$rsum$。否则直接赋值为$rc->rsum$。
• 3、计算$sum$
  这应该很好想，就直接在$lc->sum$，$rc->sum$，$lc->rsum + rc->lsum$中间取个$max$就可以了，其中最后一个有点特殊，想想也挺简单，因为$lc->rsum$和$rc->lsum$中所记录的区间是连续的（看看定义就知道了）。
• 4.计算$color$
  有了前面的经验，这个应该很简单，直接给出，脑补也不困难。
  $color = \begin{cases} 0, & \mbox{if }sum\mbox{= 0} \\ 1, & \mbox{if }sum\mbox{= r - l + 1} \\ -1, & \mbox{if}\mbox{0<sum<r - l + 1} \end{cases}$

其次是$query()$

由于本人比较蒟蒻,所以我使用了一个$struct$来存储我需要的$Ans$并逐步更新，$Ans$里面存储三个值，$ls$，$rs$和$s$，意义应该很明白，和上面的$lsum$，$rsum$，$sum$一一对应，答案的转移与$pushup()$相类似由于上面的$pushup()$使用到了$color$来简化操作，现在的$Ans$中不便维护$color$，所以不能偷懒了~。

然后就没有什么可以说的了，其余操作和原版线段树类似，如果不明白可以参考这

$Code$

struct SegTree {
    #define lc(o) o << 1 //简化操作
    #define rc(o) o << 1 | 1  
    #define mid ((l + r) >> 1)
    struct Ans { 
        int ls, rs, s; 
        Ans(int ls, int rs, int s) : ls(ls), rs(rs), s(s) {}
    };
    static const int MAXSIZE = 100000 + 5;
    int lsum[MAXSIZE << 2], rsum[MAXSIZE << 2], sum[MAXSIZE << 2], color[MAXSIZE << 2];
    void creat(int o, int l, int r, int value) { //更新一个结点
        color[o] = value;
        lsum[o] = rsum[o] = sum[o] = value ? r - l + 1 : 0; //三目运算符秀了一波~
    }
    void pushdown(int o, int l, int r) {  
        if (color[o] != -1) { //如果有color那么pushdown，注意color不会在向子结点更新后发生改变
            creat(lc(o), l, mid, color[o]);
            creat(rc(o), mid + 1, r, color[o]);
        }
    }
    void pushup(int o, int l, int r) { //繁琐的pushup()，具体已经解释过了
        lsum[o] = color[lc(o)] == 1 ? lsum[lc(o)] + lsum[rc(o)] : lsum[lc(o)];
        rsum[o] = color[rc(o)] == 1 ? rsum[lc(o)] + rsum[rc(o)] : rsum[rc(o)];
        sum[o] = max(rsum[lc(o)] + lsum[rc(o)], max(sum[lc(o)], sum[rc(o)]));
        if (sum[o] == 0) color[o] = 0; else if (sum[o] == r - l + 1) color[o] = 1; else color[o] = -1;
    }
    void set(int o, int l, int r, int L, int R, int value) { //和普通线段树一样的操作
        if (l > R || r < L) return;
        else if (L <= l && r <= R) creat(o, l, r, value);
        else {
            pushdown(o, l, r);
            set(lc(o), l, mid, L, R, value);
            set(rc(o), mid + 1, r, L, R, value);
            pushup(o, l, r);
        }
    }
    Ans query(int o, int l, int r, int L, int R) {
        if (l > R || r < L) return Ans(0, 0, 0);
        else if (L <= l && r <= R) return Ans(lsum[o], rsum[o], sum[o]);
        else {
            pushdown(o, l, r);
            if (R <= mid) return query(lc(o), l, mid, L, R);
            if (L > mid) return query(rc(o), mid + 1, r, L, R);
            Ans p = query(lc(o), l, mid, L, R);
            Ans q = query(rc(o), mid + 1, r, L, R);
            return Ans(p.ls == mid - l + 1 ? p.ls + q.ls : p.ls, 
                       q.rs == r - mid ? p.rs + q.rs : q.rs, 
                       max(max(p.s, q.s), p.rs + q.ls));
        }
    }
    void build(int o, int l, int r) {
        if (l > r) return;
        else if (l == r) creat(o, l, r, a[l]);
        else {
            build(lc(o), l, mid);
            build(rc(o), mid + 1, r);
            pushup(o, l, r);
        }
    }
};

线段树的区间合并操作

• 线段树的区间合并操作维护信息时，除了区间和、更新标记等，最重要的就是要维护lsum和rsum这两个特殊值
• 这两个值分别各自的意义是：lsum 代表以该区间左端点为起点的连续段的长度(左连续段) ，rsum代表以该区间右端点为终点（注意是终点）的连续段的长度（右连续段），而rsum[rt<<|1]+lsum[rt<<1|1]则是代表了含有当前区间终点的最大连续段长度。
• 另外还有一个需要维护的值就是 sum[rt] 也就是当前节点下的最大连续区间的长度，而对于每一次lsum和rsum更新完成后 sum[rt]应这样给出：
• sum[rt] = max(rsum[rt<<1]+lsum[rt<<1|1],max(sum[rt<<1],sum[rt<<1|1])
• 其值就在左子树最大连续区间，右子树最大连续区间和中间连续段中取最大值
• 另外 区间合并在线段树操作中主要体现在pushup函数的变化上：

void pushup(int rt,int tot)
{
	if(tot == 1) return ;
	lsum[rt] = lsum[rt<<1];
	rsum[rt] = rsum[rt<<1|1];
	// 体现区间合并的地方
	if(lsum[rt] == (tot-tot/2)) lsum[rt]+=lsum[rt<<1|1];//代表左子树的区间满了需要加上右子树左区间
	if(rsum[rt] == (tot/2)) rsum[rt]+=rsum[rt<<1];// 和上方同理
	sum[rt] = max(rsum[rt<<1]+lsum[rt<<1|1],max(sum[rt<<1],sum[rt<<1|1]));
}

POJ3667 HDU4553（比前面麻烦一点 维护两个树）
这两道题都要求返回一个查询的位置信息写在query函数中就是

int query(int rt,int l,int r,int len)// len代表需要满足的区间长度
{
	if(l == r) return l;
	pushdown(rt,r-l+1);
	int mid = (l+r)>>1;
	if(sum[rt<<1] >= len) return query(rt<<1,l,mid,len);//做子树区间满足要求 那么位置一定在左子树区间中
	else if(rsum[rt<<1]+lsum[rt<<1|1] >= len) return mid-rsum[rt<<1]+1;// 中间段满足要求 那么起始点一点是左子树右连续区间的起点
	else return query(rt<<1|1,mid+1,r,len);//其他情况就一定存在于右子树中
}

代码：

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
typedef long long ll;
const int MAXN = 5e4+7;
int sum[MAXN<<2],lsum[MAXN<<2],rsum[MAXN<<2];
int lazy[MAXN<<2];
// 这个就是 hdu4553的弱化版
// 这中区间一个起始位置的题目应该都是一个套路
// 区间合并的关键 在pushup中 而query或者其他函数需要根据具体题目具体 确定
void pushup(int rt,int tot)
{
	if(tot == 1) return ;
	lsum[rt] = lsum[rt<<1];
	rsum[rt] = rsum[rt<<1|1];
	if(lsum[rt] == (tot-tot/2)) lsum[rt]+=lsum[rt<<1|1];
	if(rsum[rt] == (tot/2)) rsum[rt]+=rsum[rt<<1];
	sum[rt] = max(rsum[rt<<1]+lsum[rt<<1|1],max(sum[rt<<1],sum[rt<<1|1]));
}

void pushdown(int rt,int tot)
{
	if(tot == 1) return ;
	if(lazy[rt]){
		lazy[rt<<1] = lazy[rt<<1|1] = lazy[rt];
		if(lazy[rt] == 2){
			sum[rt<<1] = lsum[rt<<1] = rsum[rt<<1] = tot-tot/2;
			sum[rt<<1|1] = lsum[rt<<1|1] = rsum[rt<<1|1] = tot/2;
		}
		else if(lazy[rt] == 1){
			sum[rt<<1] = lsum[rt<<1] = rsum[rt<<1] = 0;
			sum[rt<<1|1] = lsum[rt<<1|1] = rsum[rt<<1|1] = 0;
		}
		lazy[rt] = 0;
	}
}

void build(int rt,int l,int r)
{
	lazy[rt] = 0;
	if(l == r){
		sum[rt] = lsum[rt] = rsum[rt] = 1;
		return ;
	}
	//pushdown(rt,r-l+1);
	int mid = (l+r)>>1;
	build(rt<<1,l,mid);
	build(rt<<1|1,mid+1,r);
	pushup(rt,r-l+1);
}

void update(int rt,int l,int r,int ul,int ur,int p)
{
	if(l>=ul&&r<=ur){
		if(p == 1){
			sum[rt] = lsum[rt] = rsum[rt] = 0;
		}
		else if(p == 2){
			sum[rt] = lsum[rt] = rsum[rt] = r-l+1;
		}
		lazy[rt] = p;
		return ;
	}
	pushdown(rt,r-l+1);
	int mid = (l+r)>>1;
	if(ul <= mid) update(rt<<1,l,mid,ul,ur,p);
	if(ur > mid) update(rt<<1|1,mid+1,r,ul,ur,p);
	pushup(rt,r-l+1);
}

int query(int rt,int l,int r,int len)
{
	if(l == r) return l;
	pushdown(rt,r-l+1);
	int mid = (l+r)>>1;
	if(sum[rt<<1] >= len) return query(rt<<1,l,mid,len);
	else if(rsum[rt<<1]+lsum[rt<<1|1] >= len) return mid-rsum[rt<<1]+1;
	else return query(rt<<1|1,mid+1,r,len);
}

int main()
{
	int n,m;
	scanf("%d%d",&n,&m);
	build(1,1,n);
	int k;
	while(m--){
		scanf("%d",&k);
		if(k == 1){
			int len;
			scanf("%d",&len);
			if(sum[1]>=len){
				int pos = query(1,1,n,len);
				printf("%d\n",pos);
				update(1,1,n,pos,pos+len-1,1);
			}
			else printf("0\n");
		}
		else if(k == 2){
			int st,len;
			scanf("%d%d",&st,&len);
			update(1,1,n,st,st+len-1,2);
		}
	}
	return 0;
}

深入理解线段树区间合并问题