http://acm.hdu.edu.cn/showproblem.php?pid=3308&&线段树之区间合并
由于这几天学算法的情绪高涨，于是就复习了之前学的线段树，这进一步加深了对线段树的理解，顺便记录一下自己的心得：
1，做线段树题首先要考虑的是线段树中节点的属性，比如左右边界，区间和，在该区间插入的值，延迟标记，等等。
2，弄清楚孩子节点的更新对父亲节点的影响，父亲节点的更新对孩子节点的影响，从而设计好push_up()和push_down()函数。
3，在弄清前两步的基础上设计好build（),updata(),Quary(),函数，这三个函数何时需要调用push_up和push_down 函数为该部分的重点，一定不要乱了顺序
4，如果前三个步骤都得到合理解决，那么线段树问题也就不是什么问题了。。。
该题的题意就是，给你一段数，然后给你两种操作，Q表示查询一个区间的最大连续递增序列的长度，U表示改变某一个位置的值。
下面根据我上面的四个步骤一一分析一下：
1，节点属性 L,R，lsum，rsum，msum:分别表示该节点左右边界，左最长递增长度，右最长递增长度，该区间的最长递增长度
2，经过分析该题只涉及到孩子节点更新对父节点的影响，因此只需要设计push_up函数
3，build()设计很简单，updata()的设计类似于线段树插点问线的更新，最难的也是该题的难点就是Quary()的设计需要注意的是：查询时有时需要对结果进行合并。
4，分析结束。
AC代码：
[cpp]
#include <iostream>
#include<string.h>
#include<algorithm>
#include<cstdio>
#define CLR(arr,val) memset(arr,val,sizeof(arr))
#define N 100010
using namespace std;
void in(int &a)
{
char ch;
while((ch=getchar())<'0'||ch>'9');
for( a=0;ch>='0'&&ch<='9';ch=getchar()) a=a*10+ch-'0';
}
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
typedef struct{
int L;
int R;
int lsum;
int rsum;
int msum;
}Tree;
Tree Node[N<<2];
int a[N];
void push_up(int rt,int s){
Node[rt].lsum=Node[rt<<1].lsum;
Node[rt].rsum=Node[rt<<1|1].rsum;
Node[rt].msum=max(Node[rt<<1].msum,Node[rt<<1|1].msum);
if(a[Node[rt<<1].R]<a[Node[rt<<1|1].L]){
if(Node[rt<<1].lsum==(s-(s>>1))) Node[rt].lsum+=Node[rt<<1|1].lsum;
if(Node[rt<<1|1].rsum==(s>>1)) Node[rt].rsum+=Node[rt<<1].rsum;
Node[rt].msum=max(Node[rt].msum,Node[rt<<1].rsum+Node[rt<<1|1].lsum);
}
}
void build(int l,int r,int rt){
Node[rt].L=l;
Node[rt].R=r;
if(l==r){
in(a[r]);
Node[rt].lsum=Node[rt].rsum=Node[rt].msum=1;
return;
}
int m=(l+r)>>1;
build(lson);
build(rson);
push_up(rt,r-l+1);
}
void updata(int p,int l,int r,int rt)
{
if(r==l) return;
int m=(l+r)>>1;
if(p<=m) updata(p,lson);
else updata(p,rson);
push_up(rt,r-l+1);
}
int Quary(int L,int R,int l,int r,int rt){
if(l==L&&r==R) return Node[rt].msum;
int m=(l+r)>>1;
if(L>m) return Quary(L,R,rson);
else if(R<=m) return Quary(L,R,lson);
else{
int ans=max(Quary(L,m,lson),Quary(m+1,R,rson));
if(a[Node[rt<<1].R]<a[Node[rt<<1|1].L]) ans=max(ans,min(m-L+1,Node[rt<<1].rsum)+min(R-m,Node[rt<<1|1].lsum));
return ans;
}
}
int main()
{
int T;in(T);
while(T--){
int n,m;
in(n),in(m);
build(1,n,1);
char s[2];
for(int i=0;i!=m;++i)
{
scanf("%s",s);
if(s[0]=='Q'){
int b,c;
in(b),b++;
in(c),c++;
printf("%d/n",Quary(b,c,1,n,1));
}
else{
int b,c;
in(b),b++;in(c);
a[b]=c;
updata(b,1,n,1);
}
}
}
return 0;
}
//错误：建树时混淆了区间长度和左右边界的关系，在查询没有设计好合并这一种情况
