# LCIS

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<=105).
The next line has n integers(0<=val<=105).
The next m lines each has an operation:
U A B(0<=A,n , 0<=B=105)
OR
Q A B(0<=A<=B< n).
Output
For each Q, output the answer.

CPP代码：
```#include <bits/stdc++.h>
using namespace std;

#define lson l, m, rt<<1
#define rson m+1, r, rt<<1|1

const int maxn = 1e5+7;
int llen[maxn<<2], rlen[maxn<<2], mlen[maxn<<2];
int num[maxn];

void pushUp(int l, int r, int rt) {
llen[rt] = llen[rt<<1];
rlen[rt] = rlen[rt<<1|1];
mlen[rt] = max(mlen[rt<<1], mlen[rt<<1|1]);
int mid = (l + r) >> 1, len = r - l + 1;
if(num[mid] < num[mid+1]) {
if(llen[rt] == len-(len>>1)) llen[rt] += llen[rt<<1|1];
if(rlen[rt] == (len>>1)) rlen[rt] += rlen[rt<<1];
mlen[rt] = max(mlen[rt], rlen[rt<<1] + llen[rt<<1|1]);
}
}

void build(int l, int r, int rt) {
if(l == r) {
scanf("%d", &num[l]);
llen[rt] = rlen[rt] = mlen[rt] = 1;
return;
}
int m = (l+r)>>1;
build(lson);
build(rson);
pushUp(l, r, rt);
}

void update(int p, int x, int l, int r, int rt) {
if(l == r) {
num[l] = x;
return;
}
int m = (l + r) >> 1;
if(p <= m) update(p, x, lson);
else update(p, x, rson);
pushUp(l, r, rt);
}

int query(int L, int R, int l, int r, int rt) {
if(L <= l && R >= r)
return mlen[rt];
int m = (l + r) >> 1;
if(R <= m) return query(L, R, lson);
if(L > m) return query(L, R, rson);
int ta = query(L, R, lson), tb = query(L, R, rson);
int best = max(ta, tb);
if(num[m] < num[m+1]) {
ta = min(m-L+1, rlen[rt<<1]);
tb = min(R-m, llen[rt<<1|1]);
best = max(best, ta+tb);
}
return best;
}

int main() {
int T; scanf("%d", &T);
while(T--) {
int n, m; scanf("%d%d", &n, &m);
build(1, n, 1);
for (int i = 0; i < m; ++i) {
char op[3]; int x, y;
scanf("%s%d%d", op, &x, &y);
if(op[0] == 'Q') {
++x, ++y;
printf("%d\n", query(x, y, 1, n, 1));
} else {
++x;
update(x, y, 1, n, 1);
}
}
}
return 0;
}
```