自动搬运

查看原文

来自洛谷，原作者为

	流水行船CCD 果 果 没 有 特 权 ~

搬运于2025-08-24 22:23:25，当前版本为作者最后更新于2025-04-06 17:03:26，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

现有的题解似乎没有把这题解法说的很清楚？或许还是我太菜了吧。

Statement

求字典序前 $k$ 小子序列。

$n,k,|\Sigma| \le 10^5$。

Solution

$k$ 较小，首先考虑 $k$ 路归并，发现删除堆顶状态后新增状态较多且无法快速比较两子序列字典序大小。

因此考虑建立子序列自动机。由于在子序列自动机上 DFS（优先遍历字符较小的出边）只能得到本质不同的前 $k$ 小子序列，所以还需要对于每一个我们 DFS 到的状态维护它所对应的若干个本质相同子序列的结束位置，即代码中的 Endpos。

考虑转移：设当前枚举到了出边 $val$，即每一个子序列都要在末尾加入值 $val$。枚举原序列中每一个值为 $val$ 的下标 $i$，那么所有 $\operatorname{Endpos_j} < i$ 的子序列 $j$ 都可以在末尾插入 $i$，因此需要对于每一个这样的合法二元组 $(i,j)$ 在 $\operatorname{Endpos'}$ 中插入一个新的结束位置 $i$，并将 $K \gets K - 1$。

时间复杂度：由于遍历一个二元组就会使 $K$ 减少 $1$，每次需要枚举出边 $val$，$\mathcal{O}(n+K|\Sigma|\log n)$。

注意这里需要保证枚举到的每一个 $(i,j)$ 都是合法二元组方能保证复杂度，因此需要二分到第一个大于 $\min\limits_k\{ \operatorname{Endpos_k}\}$ 的 $i_0$，从它开始枚举。

瓶颈在于枚举出边，发现其实有很多 $val$ 是无法产生合法二元组的，只有那些最后一次出现位置 $> \min\limits_k\{ \operatorname{Endpos_k}\}$ 的 $val$ 才会产生合法二元组，因此维护每一种元素最后一次出现位置 $\operatorname{last}$，二分+ST 表维护 $\operatorname{last}$ 的区间最大值，每次花 $\mathcal{O}(\log V)$找到最小的可以产生合法二元组的 $val$，即可优化为 $\mathcal{O}(n+K(\log n+\log V))$，可以通过。

Code

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define REP(i, l, r) for (int i = l; i <= r; ++i)
#define PER(i, l, r) for (int i = l; i >= r; --i)
#define ld cin
#define jyt cout
const int N = 1e5 + 7;
const int V = 1e5;
namespace JoKing {
    int n, K, B, P, LG, a[N], last[17][N];
    vector<int> G[N];
    inline int rmq(int l, int r) {return LG = __lg(r - l + 1), max(last[LG][l], last[LG][r - (1 << LG) + 1]);}
    inline int nxt(int now, int value) {
        int L = value + 1, R = V, Res = V + 1;
        while (L <= R) {
            int mid = (L + R) >> 1;
            if (now < rmq(value + 1, mid)) R = mid - 1, Res = mid;
            else L = mid + 1;
        }
        return Res;
    }
    inline void Dfs(ll Hash, int now, vector<int> Endpos) {
        int value = 0;
        while (true) {
            if ((value = nxt(now, value)) > V) break;
            vector<int> NewEndpos(0); ll NewHash = (Hash * B + value) % P; 
            for (auto i = upper_bound(G[value].begin(), G[value].end(), now); i != G[value].end(); ++i) 
                for (auto j = Endpos.begin(); j != Endpos.end() && (*j) < (*i); ++j)
                    if (!(jyt << NewHash << '\n', NewEndpos.emplace_back(*i), --K)) exit(0);
            Dfs(NewHash, *NewEndpos.begin(), NewEndpos);
        }
    }
    signed main() {
        ld >> n >> K >> B >> P;
        REP(i, 1, n) ld >> a[i], last[0][a[i]] = i, G[a[i]].emplace_back(i);
        REP(i, 1, 16) REP(j, 1, V - (1 << i) + 1) last[i][j] = max(last[i - 1][j], last[i - 1][j + (1 << (i - 1))]);
        vector<int> Endpos(1, 0);
        return Dfs(0, 0, Endpos), 0; 
    }
}
signed main() {
	ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    JoKing::main(); return 0;
}