【题意】题意很简单，就是给了两个操作，一个是U A B,代表将第A个元素用B代替，还有一个是Q A B，查询[A,B]区间里面的最长上升子序列，即LCIS。（ps:这里需要注意的是LCIS为严格的上升子序列，比如5,5,5,这个序列的LCIS为1，不是为3）

【解题思路】和Hotel类似，在线段树的节点里维护三个信息，一个是节点左边的最长上升子序列，节点右边的最长上升子序列，以及跨越节点左右两边的最长上升子序列。

【具体实现】由于这里是单点更新，顾而不用延迟标记，因此这个题比HOTEL还简单一下，只需要仔细考虑一下Push_Up就可以了。那么Push_Up怎么做呢？

void Push_Up(int l,int r,int rt)
{
    lnum[rt] = lnum[rt<<1];
    rnum[rt] = rnum[rt<<1|1];
    mnum[rt] = max(mnum[rt<<1],mnum[rt<<1|1]);
    int m = (l+r)>>1;
    if(val[m]<val[m+1])
    {
        if(lnum[rt]==m-l+1) lnum[rt]+=lnum[rt<<1|1];
        if(rnum[rt]==r-m)   rnum[rt]+=rnum[rt<<1];
        mnum[rt] = max(mnum[rt],rnum[rt<<1]+lnum[rt<<1|1]);
    }
}

用子节点的信息去更新父节点的信息就可以了，当出现了跨越某个节点左右区间的情况则需要特殊的更新一下，具体实现看代码。

【AC代码】

//Created Author :just_sort
//Created Time   :2016/3/2 19:13
//Created File   :LCIS
/***************************/
#include <cstdio>
#include <cstring>
#include <cctype>
#include <iostream>
#include <algorithm>
using namespace std;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
const int maxn = 100010;
int getInt(int &x)
{
    return scanf("%d",&x);
}
int val[maxn];
int lnum[maxn<<2],rnum[maxn<<2],mnum[maxn<<2];
void Push_Up(int l,int r,int rt)
{
    lnum[rt] = lnum[rt<<1];
    rnum[rt] = rnum[rt<<1|1];
    mnum[rt] = max(mnum[rt<<1],mnum[rt<<1|1]);
    int m = (l+r)>>1;
    if(val[m]<val[m+1])
    {
        if(lnum[rt]==m-l+1) lnum[rt]+=lnum[rt<<1|1];
        if(rnum[rt]==r-m)   rnum[rt]+=rnum[rt<<1];
        mnum[rt] = max(mnum[rt],rnum[rt<<1]+lnum[rt<<1|1]);
    }
}
void Build(int l,int r,int rt)
{
    if(l==r)
    {
        lnum[rt]=rnum[rt]=mnum[rt]=1;
        return ;
    }
    int m = (l+r)>>1;
    Build(lson);
    Build(rson);
    Push_Up(l,r,rt);
}
void Update(int p,int sc,int l,int r,int rt)
{
   if(l==r){val[l]=sc; return;}
   int m = (l+r)>>1;
   if(p<=m)  Update(p,sc,lson);
   else      Update(p,sc,rson);
   Push_Up(l,r,rt);
}
int query_ans(int L,int R,int l,int r,int rt)
{
    if(L==l&&R==r)return mnum[rt];
    int m = (l+r)>>1;
    if(R<=m) return query_ans(L,R,lson);
    if(L>m)  return query_ans(L,R,rson);
    else{
        //a为在lson区间里查到的[l,m]的LCS
        //b为在rson区间里查到的[m+1,r]的LCS
        //c为跨越左右儿子区间[L,R]上的LCS
        int a = query_ans(L,m,lson);
        int b = query_ans(m+1,R,rson);
        int c = 0;
        if(val[m]<val[m+1]){
            c+=min(rnum[rt<<1],m-L+1);
            c+=min(lnum[rt<<1|1],R-m);
        }
        return max(a,max(b,c));
    }
}
int main()
{
    int n,m,tt;
    getInt(tt);
    while(tt--)
    {
       getInt(n);
       getInt(m);
       for(int i=0;i<n;i++)getInt(val[i]);
       Build(0,n-1,1);
       char op[2];
       int a,b;
       while(m--)
       {
           scanf("%s %d %d",op,&a,&b);
           if(op[0]=='U')
           {
               Update(a,b,0,n-1,1);
           }
           else
           {
               printf("%d\n",query_ans(a,b,0,n-1,1));
           }
       }
    }
    return 0;
}