# HDOJ 3308 LCIS

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<=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.

## 题解：

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);

//
//  main.cpp
//  专题9-线段树
//
//  Created by Edwin on 2019/3/2.
//
#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;
}


0 评论