题解：CF2121H Ice Baby

ddxrS · 2025-06-19 20:40:39 · 题解

题目大意

给定 n 对数 (l_i,r_i)，对于每一个 1\le k\le n，求出所有可能的整数数组 a 的最长非递减子序列的最长长度，其中 a_i\in [l_i,r_i]。

思路

考虑维护一个数组 dp，其中 dp_i 表示当最长非递减子序列的长度为 i 时，结尾的数的最小值。

可以发现，dp 数组是不递减的。考虑当前加入 l_i,r_i 对 dp 数组产生的变化。

将其分为三段 [1,L],(L,R],(R,n]，满足 \forall j\in[1,L],dp_j\le l_i，\forall j\in(L,R],l_i<dp_j\le r_i，\forall j\in(R,n],r_i<dp_j。

• 第一段中的值不会发生变化。

• 第二段中的 dp_j 可能在 dp_{j-1} 后接一个 [l_i,r_i] 中的数来变得更小。有 dp_j=\max(dp_{j-1},l_i)，实际上就是一个区间平移，然后将 dp_{L+1} 变为 l_i。

• 第三段中的数，只有 dp_{R+1} 可能会变为 \max(dp_R,l_i)=dp_R。

可以使用 multiset 维护上述过程。

#include <bits/stdc++.h>
using namespace std;
int n;
multiset<int> dp;
void solve() {
    cin>>n; 
    dp.insert(0);
    for(int i = 1, l, r; i <= n; i++) {
        cin>>l>>r;
        auto pos = dp.upper_bound(r);
        dp.insert(l);
        if(pos != dp.end()) dp.erase(pos);
        cout<<dp.size() - 1<<" \n"[i == n];
    }
    dp.clear();
}
signed main() {
#ifdef ddxrS
    freopen("sample.in", "r", stdin);
    freopen("sample.out", "w", stdout);         
#endif
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int t; cin>>t;
    while(t--) solve();
    cerr<<clock() * 1.0 / CLOCKS_PER_SEC<<'\n'; 
    return 0;
}