CF1801C 做题笔记

题目链接

一道需要挖掘一些性质的 dpt，居然独立想出来了。

本蒟蒻太菜了只会树状数组的做法，单调栈不会。

先考虑只管对答案有贡献的音乐，这当然是正确的，因为我们可以把对答案没有贡献的音乐放到最后。

对于每一首乐曲，我们也能对它进行一个简单的处理来模拟听的过程，维护一个值 $lst$，每次输入的数 $x$ 如果大于 $lst$，那么听了这个片段后答案就会加一，将 $x$ 存入数组中，否则忽略它。

假设每个音乐的好听程度为其中最美妙的片段。

处理后有一个可以感性理解的结论：无论当前听过的最好听的片段是什么，听了一首乐曲，能够使答案增加的一定是存入数组中的片段。

证明考虑反证，假设当前听过最好听的片段好听值为 $mx$，现在听乐曲 $i$，能够找到一个位置使得 $a_{i,j} \geq mx$ 且 $a_{i,j}$ 被忽略。这是显然不可能得一件事，因为如果 $a_{i,j}$ 被忽略，就说明前面有一个更好听的片段，而 $mx$ 应该先听到的是更好听的片段就忽略了 $a_{i,j}$。

再来想，有答案贡献的音乐放在一起，每个音乐的好听程度一定是递增的。

做法于是很显然了，先将所有音乐按照好听程度排序，设 $f_i$ 为考虑第 $1$ 个音乐到第 $i$ 个音乐，其中第 $i$ 个音乐必须选的最大答案，设 $mx_j$ 为第 $j$ 首乐曲的好听程度，那么大体结构就是枚举前一个听的乐曲 $j$，然后再算出听 $i$ 之后的答案，所有的取个 $\max$ 即可。

上述为 $O(n^2)$ 做法，很烂，会超时，貌似可以用单调栈优化，超时原因是没有用到 $\sum k_i \leq 200000$ 这个条件。

考虑对于每一个乐曲的转移改为枚举这个乐曲中的每一个没被忽略的片段，然后去找前面的某个乐曲 $j$，使得 $j$ 的好听程度 $<$ 这个片段的美妙值，然后就能从 $dp_j$ 转移过来，再听这个片段以及这个片段后面没有被忽略的。

很绕口，读不懂多读几遍，然后这是个单点修改求前缀最值可以用树状数组优化到 $O(n\log n)$。

代码：

#include <bits/stdc++.h>
#define int long long
#define For(i, a, b) for (int i = (a); i <= (b); i ++)
#define foR(i, a, b) for (int i = (a); i >= (b); i --)
using namespace std;
int n, x, cnt;
int c[200005], dp[200005], idx[200005];
vector <int> a[200005];
vector <int> v[200005];
void add (int x, int y) {for (; x <= 200000; x += x & -x) c[x] = max (c[x], y);}
int query (int x) {return (x == 0 ? 0 : max (query (x - (x & -x) ), c[x]) );}
void clear (int x) {for (; x <= 200000; x += x & -x) c[x] = 0;}
set <int> s;
void solve () {
    s.clear ();
    scanf ("%lld", &n);
    For (i, 1, n) {
        scanf ("%lld", &cnt);
        int last = 0;
        while (cnt --) {
            scanf ("%lld", &x);
            if (x > last) {
                a[i].push_back (x);
                last = x;
            }
        }
        s.insert (last);
        v[last].push_back (i);
    }
    cnt = 0;
    for (int i : s) for (int j : v[i]) idx[++ cnt] = j;
    int ans = 0;
    For (i, 1, n) {
        for (int j = 0; j < a[idx[i] ].size (); j ++)
            dp[i] = max (dp[i], query (a[idx[i] ][j] - 1) + (long long) (a[idx[i] ].size () ) - j);
        add (a[idx[i] ].back (), dp[i]);
        ans = max (ans, dp[i]);
    }
    cout << ans;
    For (i, 1, n) {
        clear (a[i].back () );
        v[a[i].back ()].clear ();
        a[i].clear ();
        dp[i] = 0;
    }
}
signed main () {
    int _ = 1;
    cin >> _;
    while (_ --) {
        solve ();
        cout << '\n';
    }
    return 0;
}