HDu 3308 LCIS線分ツリー

//U A B  A B
//Q A B [A , B] 
// ma_l , ma , ma_r  ， ， 
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std ;
const int maxn = 1e5 + 10 ;
#define left v<<1
#define right v<<1|1
struct node
{
    int l , r ;
    int ma_l , ma_r , ma ;
}tree[maxn<<2] ;
int h[maxn] ;
int T ;
int n , m ;
void push_up(int v)
{
    tree[v].ma_l = tree[left].ma_l ;
    tree[v].ma_r = tree[right].ma_r ;
    tree[v].ma = max(tree[left].ma , tree[right].ma) ;
    if(h[tree[left].r] < h[tree[right].l])
    {
        tree[v].ma = max(tree[v].ma , tree[left].ma_r + tree[right].ma_l) ;
        if(tree[left].r - tree[left].l + 1 == tree[v].ma_l)
        tree[v].ma_l += tree[right].ma_l ;
        if(tree[right].r - tree[right].l + 1 == tree[v].ma_r)
        tree[v].ma_r += tree[left].ma_r ;
    }
}
void build(int l , int r , int v)
{
    tree[v].l = l ;
    tree[v].r = r;
    if(l == r)
    {
        tree[v].ma_l = tree[v].ma = tree[v].ma_r = 1 ;
        return ;
    }
    int mid = (l + r) >> 1 ;
    build(l , mid , left) ;
    build(mid + 1 , r , right) ;
    push_up(v) ;
}
int query(int v , int l , int r)
{

    if(l <= tree[v].l && tree[v].r <= r)
    return tree[v].ma ;
    int mid = (tree[v].l + tree[v].r) >> 1 ;
    int ans_1 = 0 , ans_2 = 0 ,ans_3 = 0 ;
    if(l <= mid)ans_1 = query(left , l , r) ;
    if(r > mid)ans_2 = query(right , l , r) ;
    int ans = max(ans_1 , ans_2) ;
    if(h[tree[left].r] < h[tree[right].l])
    {
        ans_3 = min(tree[left].ma_r , tree[left].r - l + 1) + min(tree[right].ma_l , r - tree[right].l + 1) ;
        ans = max(ans , ans_3) ;
    }
    return ans ;
}
void update(int pos , int num ,int v)
{
    if(tree[v].l == tree[v].r)
    {
        h[pos] = num ;
        return  ;
    }
    int mid = (tree[v].l + tree[v].r) >> 1 ;
    if(pos <= mid)update(pos , num , left);
    else if(pos > mid)update(pos ,num ,right) ;
    push_up(v) ;
}
int main()
{
   // freopen("in.txt" ,"r" ,stdin) ;
    scanf("%d" , &T) ;
    while(T--)
    {
        scanf("%d%d" ,&n , &m) ;
        for(int i = 1;i <= n;i++)
        scanf("%d" , &h[i]) ;
        build(1 , n , 1) ;
        char ch[10] ;int a , b ;
        while(m--)
        {
            scanf("%s" ,ch) ;
            scanf("%d%d" ,&a , &b) ;
            if(ch[0] == 'Q')
            printf("%d
" ,query(1 , a  + 1, b + 1));
            else if(ch[0] == 'U')
            update(a+1 , b , 1) ;
        }
    }
    return 0 ;
}