CF1801C 题解

· · 题解

C

vp 完后看题解都是数据结构优化 DP，遂提供一种赛时写的图论建模做法，时间复杂度瓶颈在于离散化。

先尝试暴力的建图。将每个位置 a_{i, j} 当作节点。设点 u 能经过一条边权为 w 的边走到 v 的意义是若当前最大值的位置是 u，则存在一种方法使得最大值的位置变成 v 并对答案产生 w 的贡献。

考虑同一数列中的点如何连边。因为选择了一个数列时需要把整个数列都选上，所以每个点像数列右边第一个不小于当前点的位置连边，如果两个点相等边权赋为 0，否则赋为 1。单调栈维护一下即可。

考虑不同数列中如何连边。一个数列一定是最大值连向别的数列。设当前数列最大值为 x，则连向所有其它数列中从左到右第一个大于 x 的位置，边权为 1。

然后建个起点连向所有数列的第一个位置，再建个终点从每个数列的最大值连向它，边权均设为 0，然后在 DAG 上跑最长路就能得到答案。

为什么这是对的呢？因为这条路径上经过的点就是所有的前缀最大值，如果这条路径上没走过一个点说明这个点拼上去后也不会产生贡献。

但是这样边数炸了，每个数列最大值都连 n 条边，边数是 n^2 级别的。

考虑优化建图。

注意到不同数列之间的连边的依据是偏序关系，所以考虑在图中拉一条数轴出来，让判断偏序的连边在数轴上完成。

具体的，将在所有数列中出现过的数存起来离散化，设出现过的数有 siz 个，那么就新建 siz + 1 个点，每个点向后继连边权为 0 的边。

对于每个数列，有用的点仅有本身是前缀最大值的点。

然后就可以把原本的数列最大值连向另一个数列的一个值这一过程分为三步，从当前数列的最大值走到数轴，沿着数轴走到一个另一数列能产生贡献的点，然后再从数轴进入另一数列。

因此，对于每一数列的所有前缀最大值，从数轴上对应的点向它连一条边权为 1 的边，代表进入这一数列，并且因为选择了当前数又产生了 1 的贡献。

然后将每一数列的最大值向它在数轴上的后继节点连一条边权为 0 的边。连向后继节点是因为当前最大值已经不会产生贡献了，同时可以避免成环。

然后上面新建起点和终点的步骤就不需要了，因为数轴的起点可以直接看作起点，而数轴的终点也能看作终点。

这样建出来的图边数是 O(\sum k_i) 级别的。上界是 3\sum k_i + 1，当数列中每个数都不同，且所有数列都形成单调上升序列时取到上界。

然后在这张新 DAG 上跑最长路即可，也就是拓扑排序后跑个简单 dp 转移。

样例一建出来的图是这样的。

同一行的点代表同一数列，最上面的一排是数轴。每个点上方标注的是这个点实际表示的值。结合样例和上面的说明应该能看得懂吧。

在这张图上，1 是起点，7 是终点。有最长路 \{1, 16, 2, 3, 4, 13, 5 ,14, 6, 9, 7\}，长度为 4，则答案为 4。

按题目的表述描述成数列则为 \{1, 7, 8, 6, 4, 9, 4, 6, 8\}，前缀最大值为 \{1, 7, 8, 9\}，为上述最长路中经过的数列中的点。

Submission #280521098 - Codeforces

code：

#include<iostream>
#include<fstream>
#include<algorithm>
#include<vector>
#include<cstring>
#include<queue>
#define int long long
#define eb emplace_back
#define mp make_pair
#define DEBUG
using namespace std;
const int P = 998244353, inf = 0x3f3f3f3f3f3f3f3f;
using pii = pair<int, int>;
namespace azus{
    int n, m;
    vector<vector<pii> > edge;
    vector<int> du;
    vector<vector<int> > a;
    vector<int> l;
    vector<int> f;
    int main(){
        cin >> n, m = 0;
        l.assign(n + 5, 0);
        a.assign(n + 5, vector<int> {});
        vector<int> b;
        for(int i = 1; i <= n; i ++){
            cin >> l[i];
            a[i].assign(l[i] + 3, 0);
            for(int j = 1; j <= l[i]; j ++)
                cin >> a[i][j], b.eb(a[i][j]);
            m += l[i];
        }
        sort(b.begin(), b.end());
        auto epos = unique(b.begin(), b.end());
        b.erase(epos, b.end());
        int N = m + b.size() + 5;
        du.assign(N + 5, 0);
        f.assign(N + 5, 0);
        edge.assign(N + 5, vector<pii>{});
        for(int i = 0; i < (int)b.size(); i ++){
            edge[m + i + 1].eb(mp(m + i + 2, 0)), du[m + i + 2] ++;
        }
        auto c = a;
        int nm = 0;
        for(int i = 1; i <= n; i ++){
            int x = -1;
            for(int j = 1; j <= l[i]; j ++){
                nm ++;
                c[i][j] = lower_bound(b.begin(), b.end(), c[i][j]) - b.begin() + 1;
                if(max(x, a[i][j]) == a[i][j])
                    edge[c[i][j] + m].eb(mp(nm, 1)), du[nm] ++;
                x = max(x, a[i][j]);
            }
        }
        nm = 0;
        for(int i = 1; i <= n; i ++){
            int u = max_element(a[i].begin() + 1, a[i].begin() + l[i] + 1) - a[i].begin();
            edge[nm + u].eb(mp(c[i][u] + 1 + m, 0));
            du[c[i][u] + 1 + m] ++;
            vector<int> stk(l[i] + 5, 0);
            vector<int> cq(l[i] + 5, 0);
            int top = 0;
            for(int j = l[i]; j >= 1; j --){
                while(top && a[i][stk[top]] <= a[i][j])
                    top --;
                cq[j] = stk[top];
                stk[++ top] = j;
            }
            for(int j = 1; j <= l[i]; j ++){
                if(!cq[j]) continue;
                if(a[i][cq[j]] != a[i][j])
                    edge[nm + j].eb(mp(nm + cq[j], 1));
                else edge[nm + j].eb(mp(nm + cq[j], 0));
                du[nm + cq[j]] ++;
            }
            nm += l[i];
        }
        queue<int> q;
        vector<int> topo(N + 5, 0);
        int tot = 0;
        for(int i = 1; i <= N; i ++){
            if(du[i] == 0) q.emplace(i);
        }
        while(!q.empty()){
            int u = q.front();
            topo[++ tot] = u;
            q.pop();
            for(auto [v, w] : edge[u]){
                du[v] --;
                if(du[v] == 0) q.emplace(v);
            }
        }
        int t = m + 1 + b.size();
        for(int i = 1; i <= tot; i ++){
            int u = topo[i];
            for(auto [v, w] : edge[u]){
                f[v] = max(f[v], f[u] + w);
            }
        }
        cout << f[t] << "\n";
        return 0;
    }
}
signed main(){
#ifndef DEBUG
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
#endif
    int T = 1;
    cin >> T;
    while(T --)
        azus::main();
    return 0;
}