CF2121H Ice Baby

StayAlone · 2025-06-22 14:51:28 · 题解

官方题解精妙做法的另一种理解。

设 f_{i, j} 表示考虑前缀 i，且 a_i\le j 时的最长不下降子序列长度。

显然 f_i 是一个不降序列。每次插入 [l_i,r_i]，等价于：

1. 区间 [l_i,r_i] 加 1
2. 取前缀 \max

第二步等价于用 f_{i,r_i} 往后区间覆盖，直到第一个比 f_{i, r_i} 大的位置。

可以用线段树做，不过有更好的维护方式。

考虑用 multiset 维护 f_i 差分的“断点”，即集合中放 f_{i, j}-f_{i, j-1} 个 j。形式化地，此时 f_{i, j}=|\{v\mid v\le j\land v\in S\}|。

于是上述操作等价于，将第一个比 r 大的断点删去，并插入 l。

时间复杂度 \mathcal O(n\log n)。

AC record

il void solve() {
    read(n); multiset <int> dp;
    rep1(i, 1, n) {
        int l, r; read(l, r);
        auto it = dp.upper_bound(r);
        if (it != end(dp)) dp.erase(it);
        dp.emplace(l); cout << dp.size() << ' ';
    } puts("");
}

int main() {
    for (int T = read(); T--; ) solve();
    return 0;
}