hdu 3308线段树 区域合并

区域合并时需要考虑两点 

1、pushup中区域合并时最左右递增长度（llen/rlen）等于整个区域长度(r - l)时需要重新计算父区域的最左右的递增长度

2、query中需要考虑区域合并接口处是否有可能产生ans值

#include<iostream>
#include<stdio.h>
#include<string>
#include<string.h>

using namespace std;

const int maxn = 100050;

struct node{
	int l, r, ml;//最左右边界，最大长度 
	int lw, rw;//最左右的值 
	int llen, rlen;//最左右递增区域的长度 
	int mid(){
		return (l+r)/2;
	} 
}tree[maxn*4];

void pushUp(int left, int right, int ind)
{
	tree[ind].lw = tree[ind*2].lw;
	tree[ind].rw = tree[ind*2+1].rw;
	tree[ind].llen = tree[ind*2].llen;
	tree[ind].rlen = tree[ind*2+1].rlen;
	int len = 0;
	if( tree[ind*2].rw < tree[ind*2+1].lw ){
		len = tree[ind*2].rlen + tree[ind*2+1].llen;
		//考虑最左右递增区域等于整个区域的情况 
		if(tree[ind*2+1].llen == tree[ind*2+1].r - tree[ind*2+1].l+1){
			tree[ind].rlen = tree[ind*2+1].llen + tree[ind*2].rlen; 
		}
		if(tree[ind*2].rlen == tree[ind*2].r - tree[ind*2].l+1){
			tree[ind].llen = tree[ind*2].rlen + tree[ind*2+1].llen;
		}
	} 
	len = len > tree[ind*2].ml ? len : tree[ind*2].ml;
	tree[ind].ml = len > tree[ind*2+1].ml ? len : tree[ind*2+1].ml;
}

void buildTree(int left, int right, int ind)
{
	tree[ind].l = left;
	tree[ind].r = right;
	
	if(left == right){
	 	cin >> tree[ind].lw;
		tree[ind].rw = tree[ind].lw;
		tree[ind].llen = tree[ind].rlen = 1;
		tree[ind].ml = 1;  
		return ;
	}
	int mid = tree[ind].mid();
	buildTree(left, mid, ind*2);
	buildTree(mid+1, right, ind*2+1);
	
	pushUp(left, right, ind);
}

void update(int left, int right, int ind, int pos, int add)
{
	if(left == right){
		tree[ind].lw = tree[ind].rw = add;
		return ;
	}
	int mid = tree[ind].mid();
	if(pos <= mid) update(left, mid, ind*2, pos, add);
	if(pos > mid) update(mid+1, right, ind*2+1, pos, add);
	pushUp(left, right, ind); 
}

int ans;
void query(int left, int right, int ind, int L, int R)
{
	if(L <= left && R >= right){
		ans = ans > tree[ind].ml ? ans : tree[ind].ml;
		if(ans > 1000) cout<<"que ind"<<ind<<endl;
		return ;
	}
	
	int mid = tree[ind].mid();
	if(L <= mid){
		query(left, mid, ind*2, L, R);
	}
	if(R > mid){
		query(mid+1, right, ind*2+1, L, R);
	}
	int len;
	//考虑区间合并时左右两段相加 
	if(tree[ind*2].rw < tree[ind*2+1].lw){
		len = min(mid-L+1, tree[ind*2].rlen) + min(R-mid, tree[ind*2+1].llen);
		ans = ans > len ? ans : len;
	}
	
} 

int main()
{
	int T, m, n, a, b;
	string str; 
	scanf("%d",&T);
	while(T --)
	{
		scanf("%d%d", &n, &m);
		buildTree(1, n, 1);

		while(m --)
		{
			cin >> str;
			scanf("%d%d",&a, &b);
			if(str == "Q"){
				ans = 0;
				query(1, n, 1, a+1, b+1);
				printf("%d\n", ans);
			}
			if(str == "U"){
				update(1, n, 1, a+1, b);
			}
		}
	}
	
	return 0;
}

hdu 3308线段树 区域合并

原文：http://blog.csdn.net/u011504498/article/details/38015877