【題目敘述】https://vjudge.net/problem/HDU-3308
【解題想法】線段樹 (Segment Tree)，LIS (最長遞增子序列)
- 思考：左右兩個區間的LIS長度該怎麼pushup？
- arr[maxn]：存放讀入的數值
- struct node：定義線段樹每個節點存放的資料，開4倍空間
- l, r：每個節點覆蓋區間的左界和右界
- L：區間從最左端(包含)的最長遞增子序列長度
- R：區間從最右端(包含)的最長遞增子序列長度
- mx：[l, r] 區間內的最長遞增子序列長度
- pull( )：依node的資料結構定義進行
- query( )：
- 當一個節點覆蓋的區間 [l, r] 完全落於 [ql, qr] 區間內，回傳該節點
- 依照 [ql, qr] 要求，搜尋左兒子 and/or 右兒子
- 回傳的節點，需再進行pull( )，計算出真正的LIS長度
#include <iostream>
#include <cmath>
using namespace std;
struct node{
//區間 [l, r]
//L：區間從左往右的最長遞增子序列長度
//R：區間從右往左的最長遞減子序列長度
//mx：區間內的最長遞增子序列長度
int l, r, L, R, mx;
};
int n, m, Case, a, b, arr[100005];
char c;
node lis[100005 << 2];
void pull(node &x, node l, node r){
x.l = l.l;
x.r = r.r;
x.L = l.L;
x.R = r.R;
x.mx = max(l.mx, r.mx);
if (arr[l.r] < arr[r.l]){
x.mx = max(x.mx, l.R + r.L);
if (l.R == l.r-l.l+1) x.L = max(x.L, x.mx);
if (r.L == r.r-r.l+1) x.R = max(x.R, x.mx);
}
}
void build(int x, int l, int r){
if (l == r){
lis[x].l = l;
lis[x].r = r;
lis[x].L = 1;
lis[x].R = 1;
lis[x].mx = 1;
return;
}
int mid = (l + r) >> 1;
build(x<<1, l, mid);
build(x<<1|1, mid+1, r);
pull(lis[x], lis[x<<1], lis[x<<1|1]);
}
node query(int x, int l, int r, int ql, int qr){
if(ql <= l && r <= qr){
return lis[x];
}
int mid = (l + r) >> 1;
if(qr <= mid){
return query(x<<1, l, mid, ql, qr);
}else if(mid < ql){
return query(x<<1|1, mid+1, r, ql, qr);
}else{
node left = query(x<<1, l, mid, ql, qr);
node right = query(x<<1|1, mid+1, r, ql, qr);
node ans;
pull(ans, left, right);
return ans;
}
}
void update(int x, int l, int r){
if (l == r){
arr[a] = b;
return;
}
int mid = (l + r) >> 1;
if (a <= mid) update(x<<1, l, mid);
else update(x<<1|1, mid+1, r);
pull(lis[x], lis[x<<1], lis[x<<1|1]);
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> Case;
while (Case--){
cin >> n >> m;
for (int i = 1; i <= n; i++){
cin >> arr[i];
}
build(1, 1, n);
for (int i = 0; i < m; i++){
cin >> c >> a >> b;
a++;
if (c == 'Q'){
b++;
cout << query(1, 1, n, a, b).mx << "\n";
}else{
update(1, 1, n);
}
}
}
}