Brief description:
… 动态维护一个数组 A[]，支持以下两种操作
U a b: 单点修改，将 A[a] 替换成 b。(从 0 标号。。)Q a b: 区间询问，询问 [a, b] 区间的 LCIS (Longest Continuous Increase Subsequence, 最长连续递增子序列) 的长度。
Analysis:
struct Seg{
int ll, rr, ss;
} T[4*N];
...
void Update(int x, int l, int r){
T[x].ll = T[lx].ll, T[x].rr = T[rx].rr;
T[x].ss = max(T[lx].ss, T[rx].ss);
if (A[ml] < A[mr]){
if (T[x].ll == mr - l) T[x].ll += T[rx].ll;
if (T[x].rr == r - ml) T[x].rr += T[lx].rr;
checkMax(T[x].ss, T[lx].rr + T[rx].ll);
}
}
http://acm.hust.edu.cn/vjudge/contest/viewSource.action?id=3946299
External link:
…
