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:

…

Posted by xiaodao
Category: Online Judge