动态LCIS问题：动态的最长连续上升子序列。
如果该序列是静态的，那么既可用线段树的区间合并操作来求解LCIS，又可以使用动态规划方式来求解。如果该序列是动态的，不断地要更新序列的权重并且进行及时的LCIS求解，此时如果依旧使用DP方式，难免过于耗时，因为动态规划方式，是进行预处理，之后缩短查询的时间，但是一旦序列是动态之后，需要不断地预处理，非常耗时。故使用线段树的区间合并操作来解决动态LCIS问题。线段树-区间合并：
在结构体中定义变量lv、mv、rv。其中lv、rv表示，该区间从最左侧、最右侧第一个数开始的LCIS长度，mv表示中间不包括两个端点的LCIS长度。push_up函数，一个父亲区间的lv、rv应该初始化为子区间的lv、rv，mv应该初始化为左右孩子中mv大者。此时需要通过比较连接处的大小关系决定三个参数的修改，求改参数的前提是number[mid] < number[mid+1]，此时如果左孩子的lv长度是左孩子的区间长度，那么父亲的lv参数应该更改为 左孩子的lv + 右孩子的lv；如果右孩子的rv长度等于右孩子的区间长度，那么其父亲的rv参数应该更改为 右孩子的rv + 左孩子的rv；因为左右孩子是可以链接的，所以如果连接处的LCIS大于左右孩子的mv，那么此时父亲的mv应该更改为，左孩子的rv + 右孩子的lv。（这一段描述在push_up函数中有着清晰的体现）在构建线段树的时候就需要进行push_up操作。之后的updata操作也是需要的。配题：HDU 3308
题意：言简意赅，动态的LCIS问题。U操作是更改数字，Q操作是查询指定区间的LCIS大小。
#include<iostream> #include<cstring> #include<cstdio> #define L(x) x << 1 #define R(x) (x << 1) | 1 using namespace std; const int maxn = 100000 + 5; struct NODE { int lft, rht; int lv, mv, rv; int mid() { return (lft + rht) / 2; } }; NODE segtree[maxn*4]; int n, m; int number[maxn]; int Max(int x, int y) { if (x > y) return x; return y; } int Min(int x, int y) { if (x < y) return x; return y; } void push_up(int cur_index) { segtree[cur_index].lv = segtree[L(cur_index)].lv; segtree[cur_index].rv = segtree[R(cur_index)].rv; segtree[cur_index].mv = Max(segtree[L(cur_index)].mv, segtree[R(cur_index)].mv); int mid = segtree[cur_index].mid(); if (number[mid] < number[mid+1]) { if (segtree[L(cur_index)].lv == segtree[L(cur_index)].rht - segtree[L(cur_index)].lft + 1) { segtree[cur_index].lv += segtree[R(cur_index)].lv; } if (segtree[R(cur_index)].rv == segtree[R(cur_index)].rht - segtree[R(cur_index)].lft + 1) { segtree[cur_index].rv += segtree[L(cur_index)].rv; } segtree[cur_index].mv = Max(segtree[cur_index].mv, segtree[L(cur_index)].rv + segtree[R(cur_index)].lv); } } void build_segtree(int cur_index, int lft, int rht) { segtree[cur_index].lft = lft; segtree[cur_index].rht = rht; if (lft == rht) { segtree[cur_index].lv = segtree[cur_index].mv = segtree[cur_index].rv = 1; return; } else { int mid = segtree[cur_index].mid(); build_segtree(L(cur_index), lft, mid); build_segtree(R(cur_index), mid+1, rht); push_up(cur_index); } } void updata_segtree(int cur_index, int pos) { int lft = segtree[cur_index].lft; int rht = segtree[cur_index].rht; if (lft == rht) { return; } else { int mid = segtree[cur_index].mid(); if (pos <= mid) updata_segtree(L(cur_index), pos); else updata_segtree(R(cur_index), pos); push_up(cur_index); } } int query_segtree(int cur_index, int pos_lft, int pos_rht) { int lft = segtree[cur_index].lft; int rht = segtree[cur_index].rht; if (pos_lft <= lft && rht <= pos_rht) { return segtree[cur_index].mv; } else { int mid = segtree[cur_index].mid(); int resmax = 0; if (pos_lft <= mid) resmax = Max(resmax, query_segtree(L(cur_index), pos_lft, pos_rht)); if (pos_rht > mid) resmax = Max(resmax, query_segtree(R(cur_index), pos_lft, pos_rht)); if (number[mid] < number[mid+1]) { resmax = Max(resmax, Min(mid-pos_lft+1, segtree[L(cur_index)].rv) + Min(pos_rht-mid-1+1, segtree[R(cur_index)].lv)); } return resmax; } } int main() { int T; cin>> T; while (T--) { cin>> n>> m; for (int i = 1; i <= n; i++) { cin>> number[i]; } build_segtree(1, 1, n); for(int i = 1; i <= m; i++) { char op[3]; int x, y; cin>> op>> x>> y; if (op[0] == 'U') { x++; number[x] = y; updata_segtree(1, x); } else { x++; y++; cout<< query_segtree(1, x, y)<< endl; } } } return 0; }
