Time Limit: 6000/2000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)

Problem Description

Given n integers.
You have two operations:
U A B: replace the Ath number by B. (index counting from 0)
Q A B: output the length of the longest consecutive increasing subsequence (LCIS) in [a, b].

Input

T in the first line, indicating the case number.
Each case starts with two integers n , m(0<n,m<=10⁵).
The next line has n integers(0<=val<=10⁵).
The next m lines each has an operation:
U A B(0<=A,n , 0<=B=10⁵)
OR
Q A B(0<=A<=B< n).

Output

For each Q, output the answer.

题解：

线段树的单点更新,区间合并，求最大连续递增子串。

需要注意的是PushUp操作时有两种情况：

1. 左儿子最右边的值 < 右儿子最左边的值
   

    lMax = (左儿子的lMax == 左儿子的len) ? 左儿子的len + 右儿子的lMax : 左儿子的lMax;

    rMax = (右儿子的rMax == 右儿子的len) ? 右儿子的len + 左儿子的rMax : 右儿子的rMax;

    Max  = MAX(左儿子的rMax + 右儿子的lMax, 左儿子的Max, 右儿子的Max, lMax, rMax);

2. 左儿子最右边的值 >= 右儿子最左边的值

    lMax = 左儿子的lMax;

    rMax = 右儿子的rMax;

    Max  = MAX(左儿子的Max, 右儿子的Max);

由于一个区间[L,R]内的LCIS可能在左儿子,也可能跨越两边,也可能在右儿子,所以对于任意区间的LCIS查询需要递归查询左右儿子的LCIS并且还要递归查询左儿子的最长上升后缀和右儿子的最长上升前缀。

//
//  main.cpp
//  专题9-线段树
//
//  Created by Edwin on 2019/3/2.
//  Copyright © 2019 Edwin. All rights reserved.
//
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define INF 0x3f3f3f3f
#define eps 1e-8
#define maxn 100000+10
#define PI acos(-1.0)
#define mst(a,b) memset(a,b,sizeof(a))
#define FF(i,a) for(int i=0;i<a;++i)
#define FORD(i,a,b) for(int i=a;i>=b;--i)
#define FOR(i,a,b) for(int i=a;i<=b;++i)
#define sc(t) scanf("%d",&(t))
#define sc2(t,x) scanf("%d%d",&(t),&(x))
#define pr(t) printf("%d\n",(t))
#define pb push_back
#define quickcin ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define lson rt*2,l,m
#define rson rt*2+1,m+1,r
#define root 1,0,n-1
#define delf int m = (r + l) / 2
using namespace std;
int val[maxn];
int sub[maxn<<2], pre[maxn<<2], suf[maxn<<2];//最长上升子串，最长上升前缀，最长上升后缀
void PushUp(int rt, int l, int r){
    delf;
    sub[rt] = max(sub[rt<<1], sub[rt<<1|1]);
    if(val[m] < val[m + 1]) sub[rt] = max(sub[rt], suf[rt<<1] + pre[rt<<1|1]);
    pre[rt] = pre[rt<<1];
    if(pre[rt] == m - l + 1 && val[m] < val[m + 1]) pre[rt] += pre[rt<<1|1];
    suf[rt] = suf[rt<<1|1];
    if(suf[rt] == r - m && val[m] < val[m + 1]) suf[rt] += suf[rt<<1];
}

void build(int rt, int l, int r){
    if(l == r){
        sub[rt] = pre[rt] = suf[rt] = 1;//初始化
        return ;
    }
    delf;
    build(lson);
    build(rson);
    PushUp(rt, l, r);
}

//将q号元素的值置换为v
void update(int q, int v, int rt, int l, int r){
    if(l == r){
        val[l] = v;
        sub[rt] = pre[rt] = suf[rt] = 1;
        return ;
    }
    delf;
    if(q <= m) update(q, v, lson);
    else update(q, v, rson);
    PushUp(rt, l, r);
}

int query(int ql,int qr,int rt,int l,int r){
    if(ql<=l && r<=qr){ //[ql,qr]包含[l,r]
        return sub[rt];
    }
    delf;
    if(qr<=m) return query(ql,qr,lson);
    else if(m<ql) return query(ql,qr,rson);
    int res=max(query(ql,qr,lson),query(ql,qr,rson));
    int prex=min(qr-m, pre[rt<<1|1]);//[m+1,qr]与[m+1,r]相交部分的最大前缀
    int sufx=min(m-ql+1, suf[rt<<1]);//[ql,m]与[l,m]的最大后缀
    if(val[m]<val[m+1]) res=max(res,prex+sufx);
    return res;
}
int main(){
    int T, n, q;
    sc(T);
    while(T--){
        sc2(n,q);
        FF(i,n)
            sc(val[i]);
        build(root);
        while(q--){
            char str[11];
            int x, y;
            scanf("%s%d%d", str, &x, &y);
            if(str[0] == 'U')
                update(x, y, root);
            else if(str[0] == 'Q')
                printf("%d\n", query(x, y, root));
        }
    }
    return 0;
}