由於這幾天學算法的情緒高漲，於是就復習了之前學的線段樹，這進一步加深了對線段樹的理解，順便記錄一下自己的心得：
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;
}
//錯誤：建樹時混淆了區間長度和左右邊界的關系，在查詢沒有設計好合並這一種情況
