F - Permutation Division¶

题意¶

$1,2,\ldots,N$ の順列 $P$ が与えられます。

あなたは好きなように $P$ をちょうど $K$ 個の非空な連続部分列に分割することができます。

maroon 君はあなたの分割した連続部分列を並び替え、連結して、新しく順列 $Q$ を作ります。maroon 君は $Q$ を辞書順で最大にしようとします。

あなたは $Q$ が辞書順で最小になるように $P$ を連続部分列に分割したいです。そのときの $Q$ を求めてください。

解析¶

若 $K \ge P_1$ ，则将序列从 $1,2,\ldots,K$ 处分割开。这是最优的方案，因为任何其它的方案的第一个数都会大于 $K$ 。

若 $K < P_1$ ，则序列会从 $P_1$ 和 $1,2,\ldots,P_1-1$ 中的 $K-1$ 个数处分割开。显然， $Q\ge P$ ，则 $Q$ 和 $P$ 的公共前缀越长， $Q$ 越小。我们希望最大化 $Q$ 和 $P$ 的公共前缀。

考虑一段前缀 $Q[1\ldots i]$ 。这段前缀是由我们划分出的 $m$ 个连续段 $P[s_1\ldots s_2-1],P[s_2,s_3-1],\ldots,P[s_m\ldots i]$ 拼成的，且 $P[s_1]>P[s_2]>\ldots>P[s_m]$ 。由于划分的段越多， $Q$ 就越大，我们希望在 $P[s_m]$ 一定时 $P[i+1\ldots N]$ 的划分段数尽量少。

设 $dp_i$ 表示当 $Q$ 和 $P$ 的公共前缀的最后一个连续段的开头为 $i$ 时， $Q$ 和 $P$ 的公共前缀至多划分的段数。这事实上等价于求最长下降子序列的长度，可以利用树状数组在 $O(N\log N)$ 时间内解决。

对于每个作为公共前缀的最后一个连续段的开头的 $i$ ，设 $t$ 为 $P[i+1\ldots N]$ 中小于 $P[i]$ 的数的个数。 $dp_i+t\ge K$ 必须成立，否则无法为 $P[i+1\ldots N]$ 分段，使得它们中所有数在 $Q$ 中的位置都在 $P[i]$ 的位置的后面。

当 $dp_i+t\ge K$ 成立时，我们取最大的 $j$ 满足 $P[j+1\ldots N]$ 中小于 $P[i]$ 的数的个数不少于 $K-dp_i$ (※)，然后将 $P[i\ldots j]$ 归为一段，从而最大化 $Q$ 和 $P$ 公共前缀的长度。 $P[j+1\ldots N]$ 这一部分由于只有 $K-dp_i$ 个小于 $P[i]$ 的数可以作为划分出的一段的开头，则其划分方式是唯一的。

所有合法的 $i$ 中，对应的 $j$ 最大的那个对应了最长的公共前缀，为最优解。如果有多个 $i$ 对应的 $j$ 一样大，我们取 $dp_i$ 大的那个，这样后面部分划分的段数 $K-dp_i$ 最小。

(※) 如果从大到小枚举 $i$ ， $j$ 的值可以用可持久化线段树以 $O(N\log^2 N)$ 的复杂度求出；如果从小到大枚举 $P_i$ ， $j$ 的值可以用树状数组倍增以 $O(N\log N)$ 的时间复杂度求出。

实现¶

#include <bits/stdc++.h>

const int maxn = 2e5 + 19;

int n, k, p[maxn], pos[maxn], dp[maxn];

struct rmq{
    int tr[maxn];
    void update(int x, int k){
        for(; x <= n; x += x & -x)
            tr[x] = std::max(tr[x], k);
    }
    int query(int x){
        int res = -1e9;
        for(; x; x -= x & -x)
            res = std::max(res, tr[x]);
        return res;
    }
}mr;

struct binary{
    int tr[maxn];
    void update(int x, int k){
        for(; x <= n; x += x & -x)
            tr[x] += k;
    }
    int count(int x){
        int res = 0;
        for(; x; x -= x & -x)
            res += tr[x];
        return res;
    }
    int query(int x){
        int res = 0, val = 0;
        for(int i = 17; ~i; --i)
            if(res + (1 << i) <= n && val + tr[res + (1 << i)] <= x)
                val += tr[res += 1 << i];
        return res;
    }
}mt;

std::pair<int, int> ans;

void output(int l, int k){
    if(l > n) return;
    std::vector<int> a;
    for(int i = l; i <= n; ++i)
        a.push_back(i);
    std::sort(a.begin(), a.end(), [](const int &x, const int &y){
        return p[x] < p[y];
    });
    static bool vist[maxn];
    for(int i = 0; i < k; ++i)
        vist[a[i]] = true;
    for(int i = k - 1; i >= 0; --i){
        std::printf("%d ", p[a[i]]);
        for(int j = a[i] + 1; j <= n && !vist[j]; ++j)
            std::printf("%d ", p[j]);
    }
}

int main(){
    std::scanf("%d%d", &n, &k);
    for(int i = 1; i <= n; ++i)
        std::scanf("%d", p + i), pos[p[i]] = i;
    if(k >= p[1])
        return output(1, k), 0;
    std::fill(mr.tr, mr.tr + n + 1, -1e9);
    dp[1] = 1, mr.update(n - p[1] + 1, dp[1]);
    for(int i = 2; i <= n; ++i){
        dp[i] = mr.query(n - p[i] + 1) + 1;
        mr.update(n - p[i] + 1, dp[i]);
    }
    for(int i = 1; i <= n; ++i){
        int node = pos[i];
        mt.update(node, 1);
        if(dp[node] + i - mt.count(node) < k) continue;
        ans = std::max(ans, std::make_pair(mt.query(dp[node] + i - k), dp[node] - k));
    }
    ans.second = -ans.second;
    for(int i = 1; i <= ans.first; ++i)
        std::printf("%d ", p[i]);
    output(ans.first + 1, ans.second);
}

来源¶

AtCoder Regular Contest 114 F - Permutation Division

F - Permutation Division¶

题意¶

解析¶

实现¶

来源¶

评论