hdu3308 LCIS(線段樹區間合並)

題目鏈接：hdu3308

/*hdu3308 LCIS 線段樹區間合並
題目大意：
    求一段區間內的連續最長
思路：
    記錄以區間左端點開始的LCIS，以區間右端點結尾的LCIS以及整個區間的LCIS，
區間左端點的數和區間右端點的數。
更新和建樹操作都應更到葉子節點，只有葉子節點的信息時可以直接得出，然後
遞歸回到父節點，父節點可以根據左右孩子的信息來更新自己
*/
#include 
#include 
#include 
#include 
#include 
using namespace std;
#define lson l, m, rt<<1
#define rson m+1, r, rt<<1|1
const int N = 200005;
struct node
{
    int lnum, rnum;//區間最左端的數和最右端的數
    int llen;//以左端點開始的連續最長
    int rlen;//以右端點結束的連續最長
    int mlen;//區間內的連續最長
}s[N<<2];
void pushup(int rt, int m)
{
    s[rt].lnum = s[rt<<1].lnum;
    s[rt].rnum = s[rt<<1|1].rnum;
    s[rt].llen = s[rt<<1].llen;
    s[rt].rlen = s[rt<<1|1].rlen;
    s[rt].mlen = max(s[rt<<1].mlen, s[rt<<1|1].mlen);
    if(s[rt<<1].rnum < s[rt<<1|1].lnum)//左兒子的右端點<右兒子的左端點
    {
        if(s[rt].llen == m - (m>>1))//左兒子表示的區間裡的所有數，連續遞增
            s[rt].llen += s[rt<<1|1].llen;
        if(s[rt].rlen == (m>>1))//右兒子表示的區間裡的所有數，連續遞增
            s[rt].rlen += s[rt<<1].rlen;
        s[rt].mlen = max(s[rt<<1].rlen + s[rt<<1|1].llen, s[rt].mlen);//左兒子的右連續長度+右兒子的左連續長度
    }
}
void build(int l, int r, int rt)
{
    s[rt].llen = s[rt].rlen = s[rt].mlen = 1;
    if(l == r)
    {
        scanf("%d",&s[rt].lnum);
        s[rt].rnum = s[rt].lnum;
        return;
    }
    int m = (l+r) >> 1;
    build(lson);
    build(rson);
    pushup(rt, r-l+1);
}
void update(int pos, int num, int l, int r, int rt)
{
    if(l == pos && pos == r)
    {
        s[rt].llen = s[rt].rlen = s[rt].mlen = 1;
        s[rt].lnum = s[rt].rnum = num;
        return;
    }
    int m = (l+r) >> 1;
    if(pos <= m) update(pos, num, lson);
    else update(pos, num, rson);
    pushup(rt, r-l+1);
}
int query(int L, int R, int l, int r, int rt)
{
    if(L <= l && r <= R)
    {
        return s[rt].mlen;
    }
    int m = (l+r) >> 1;
    int ans = 0;
    if(L <= m)
        ans = max(ans, query(L, R, lson));
    if(m < R)
        ans = max(ans, query(L, R, rson));
    if(s[rt<<1].rnum < s[rt<<1|1].lnum)
        ans = max(ans, min(m-L+1,s[rt<<1].rlen) + min(R-m, s[rt<<1|1].llen) );
    return ans;
}
int main()
{
    int T,n,m;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d",&n,&m);
        build(1, n, 1);
        char a[2];
        int x,y;
        while(m--)
        {
            scanf("%s%d%d",a,&x,&y);
            if(a[0] == 'Q')
                printf("%d\n",query(x+1, y+1, 1, n, 1));
            if(a[0] == 'U')
                update(x+1, y, 1, n, 1);
        }
    }
    return 0;
}