hdu 3308 LCIS(线段树区间合并)

#include<stdio.h>  
#include<string.h>  
const int N=100100;  
int a[N];  
struct Tree  
{  
    int L,R,ml;  
    int Ll,Rl,Ln,Rn;  
    //ml区间的LCIS长度  
    //Ll,Rl区间左边右边的LCIS长度  
    //Ln,Rn区间左右的值  
}T[N*3];  
int max(int a,int b)  
{  
    if(a>b)return a;  
    return b;  
}  
int min(int a,int b)  
{  
    if(a<b)return a;  
    return b;  
}  
void buildTree(int L,int R,int id)  
{  
    T[id].L=L;T[id].R=R;  
    if(L==R)  
    {  
        T[id].Ln=T[id].Rn=a[L];  
        T[id].ml=T[id].Ll=T[id].Rl=1;  
        return ;  
    }  
    int mid=(L+R)>>1,li=id<<1,ri=li+1;  
    buildTree(L,mid,id<<1);  
    buildTree(mid+1,R,id<<1|1);  
    T[id].Ln=T[li].Ln;T[id].Rn=T[ri].Rn;  
    T[id].Ll=T[li].Ll;T[id].Rl=T[ri].Rl;  
    T[id].ml=max(T[li].ml,T[ri].ml);  
    if(T[li].Rn<T[ri].Ln)//左区间和右区间可以合并  
    {  
        T[id].ml=max(T[id].ml,T[li].Rl+T[ri].Ll);  
        if(T[li].Rl==mid-T[li].L+1)//左区间整个区间是LCIS，更新该区间的左边LCIS长度。  
            T[id].Ll=T[li].Ll+T[ri].Ll;  
        if(T[ri].Rl==T[ri].R-mid)  
            T[id].Rl=T[li].Rl+T[ri].Rl;           
    }  
}  
void insert(int LR,int w,int id)  
{  
    if(T[id].L==T[id].R)  
    {  
        T[id].Ln=T[id].Rn=w;  
        return ;  
    }  
    int mid=(T[id].L+T[id].R)>>1,li=id<<1,ri=li+1;  
    if(LR<=mid)insert(LR,w,li);  
    else insert(LR,w,ri);  
    T[id].Ln=T[li].Ln;T[id].Rn=T[ri].Rn;  
    T[id].Ll=T[li].Ll;T[id].Rl=T[ri].Rl;  
    T[id].ml=max(T[li].ml,T[ri].ml);  
    if(T[li].Rn<T[ri].Ln)  
    {  
        T[id].ml=max(T[id].ml,T[li].Rl+T[ri].Ll);  
        if(T[li].Rl==mid-T[li].L+1)  
            T[id].Ll=T[li].Ll+T[ri].Ll;  
        if(T[ri].Rl==T[ri].R-mid)  
            T[id].Rl=T[li].Rl+T[ri].Rl;           
    }  
}  
int query(int L,int R,int id)  
{  
    if(T[id].L==L&&T[id].R==R)  
        return T[id].ml;  
    int mid=(T[id].L+T[id].R)>>1,li=id<<1,ri=li+1;  
    if(mid>=R)  
        return query(L,R,li);  
    else if(mid<L) return query(L,R,ri);  
    else   
    {  
        int ls=query(L,mid,li);  
        int rs=query(mid+1,R,ri);  
        int ps=0;  
        if(T[li].Rn<T[ri].Ln)//左右两区间可以合并  
            ps=min(mid-L+1,T[li].Rl)+min(R-mid,T[ri].Ll);//合并的长度  
        return max(ps,max(ls,rs));  
    }  
}  
int main()  
{  
    int i,x,y,n,m,t;  
    char str[10];  
    scanf("%d",&t);  
    while(t--)  
    {  
        scanf("%d%d",&n,&m);  
        for(i=1;i<=n;i++)  
            scanf("%d",&a[i]);  
        buildTree(1,n,1);  
        while(m--)  
        {  
            scanf("%s%d%d",str,&x,&y);  
            if(str[0]=='Q')  
                printf("%d\n",query(x+1,y+1,1));  
            else insert(x+1,y,1);                 
        }  
    }  
    return 0;  
}