洛谷 P9770 [HUSTFC 2023] 逆 KMP 题解

· · 题解

线下菜比选手来写一篇题解

感觉这题很需要选手通过手玩一些例子发现性质，所以希望大家在阅读这篇题解的同时手玩一下我举出的例子来增进理解。

容易发现若给的是严格的 kmp 算法求出的前缀函数 next 数组，我们容易还原出一个唯一的答案。怎么做呢？显然有若 next(i) = j，则 num(i) = num(j)。那用并查集把每个 i 和 next(i) 合并起来就好了。

然而给的 a 并不是 next 数组，我们考虑通过还原 next 数组，再求出答案。

我们发现事实上 a 数组应该是对 next 数组的一个限制，有 next(i) \geq a(i)。

容易发现另一个限制 next(i - 1) \geq next(i) - 1。

使数字的种类变多，就是让重复数字变少。next 本身会导致两端数字相同，因此我们希望 next 尽可能小。

所以我们就要在以上两个限制下，找到一个尽可能小的 next 数组。

举个例子：

8
0 0 0 0 3 0 0 2

容易还原出 next

0 0 1 2 3 0 1 2

然后意识到，可能会出现两段重合的例子，比如：

9
0 0 0 0 0 3 0 3 0

其 next 好像是

0 0 0 1 2 3 2 3 0

但是实际上不对，你尝试一下把答案还原出来就会发现端倪。

在位置 5 处，有后面那个 3 给出一个信息：next(5) = 1，其本身自带的 a 数组又给出信息 next(5) = 3。

显然要取个 max，但是事实上不仅仅是取个 max，发现其还隐含信息 next(3) = 1。也即有结论：若两个信息重合 next(i) = a,\ b\ (a > b)，说明 next(a) = b。

所以真正的 next 应该是

0 0 1 1 2 3 2 3 0

当然，不一定仅仅只有两个重合，但是多个重合的情况大体上差不多。这时容易想到一个大力并查集的暴力：

对于每个 a(i)，我们从后往前每次减一直至 0，沿途经过的位置，其 next 对我当前推过来的数取 max，然后把重复的信息用并查集把他们对应的位置合并起来。同一个集合里的位置上的数应该是一样的。

举个例子吧：

10
0 0 0 0 4 0 0 4 0 6

大家自己尝试一下把答案求出来。

这个暴力还是不够优秀，我们需要更多的性质和结论优化它。

把结论扩展：

假设某位置 i 被后面的 a 给出了 next(i) = a, b, c, d,\dots 的信息，其中 a > b > c > d > \dots

则有 next(i) = a, next(a) = b,next(b) = c,\dots。

又有：若 next(a) = b, 则所有 b 的 next 都是 a 的 next。

容易发现 next(i) = a, b, c, d, \dots 一定会把 a 及其所有包含的 next，b 及其所有包含的 next, \dots 全部合在一起成为一个形如 next(x) = y, next(y) = z\dots 的 next 长串。

我们用大根堆和并查集维护这个长串。

假设某个堆里维护着位置 i 对应的那个长串，设堆顶为 y，则有 next(i) = y，毋庸置疑。

用完之后，这个堆接着就应当由 y 继承。但是 y 不仅需要从 i 这里继承一个堆，当然还要考虑到 a(y) 本身给了 next(y) = a(y) 以及 next(y + 1) 给了 next(y) = next(y + 1) - 1 两个信息，所以 y 真正的长串还需要加入 a(y) 及其 next，next(y + 1) - 1 及其 next。

现在问题在于，a(y) 及其 next 们不一定对应着一个堆（因为堆里可能有着更大的元素）。好在这不影响我们求出 next(y)，我们取个 max 即可。

接下来这个堆去往何方？堆里的次次大值吗？事实上 a(y) 和 next(y + 1) - 1 也成为了合法继承人之一，所以我们把他们加进堆里。然后我们就发现这个堆似乎不是在维护对应的长串了，因为 a(y) 的 next 们和 next(y + 1) - 1 的 next 们还没被放进来呢。

但是我们发现，这不影响堆里比 a(y) 和 next(y + 1) - 1 大的位置的答案。而对于 a(y) 与 next(y + 1) - 1，我们发现，如果把大于它们的位置先全处理了，那么它的 next 们虽然不存在于一个堆里，但是把其需要继承的堆全合并起来就是完整的 next 们了。

所以我们用并查集和堆启发式合并来维护这个过程。我们发现堆里的总元素个数是 O(n) 的，所以复杂度是 O(n\log^2n)，写可并堆就是严格 O(n \log n) 的了。

参考代码

#include <queue>
#include <cstdio>
#include <cctype>
#include <cstdint>
#include <iostream>
#include <algorithm>

using i32 = int32_t;
using i64 = int64_t;

#define read std::cin

const int N = 2e5 + 10;

int n;
int vis[N];
int nex[N], fa[N];
std::priority_queue<int> heap[N]; 

int find(int x) { return x == fa[x] ? x : fa[x] = find(fa[x]); }
void merge(i32 x, i32 y)
{
    x = find(x), y = find(y);
    if (x == y) return;
    if (x < y) std::swap(x, y);
    if (heap[x].size() > heap[y].size()) std::swap(heap[x], heap[y]);
    fa[x] = y;
    while (heap[x].size()) {
        heap[y].emplace(heap[x].top());
        heap[x].pop();
    }
}

int main(void)
{
    //Think twice, code once!
    std::ios::sync_with_stdio(false);
    read >> n;
    for (i32 i = 1; i <= n; ++i) {
        fa[i] = i;
        heap[i].emplace(i);
        read >> nex[i];
    }
    for (i32 i = n; i >= 1; --i) {
        auto& hp = heap[find(i)];
        while (hp.size() && hp.top() >= i) hp.pop();
        if (nex[i]) {
            hp.emplace(nex[i]);
        }
        if (nex[i + 1] > 1) {
            hp.emplace(nex[i +1] - 1);
        }
        nex[i] = hp.size() ? hp.top() : 0;
        merge(i, nex[i]);
    }
    for (int i = 1; i <= n; ++i) {
        fa[i] = i;
    }
    i32 res = 1;
    for (i32 i = 1; i <= n; ++i) {
        if (nex[i]) fa[find(i)] = find(nex[i]);
    }
    for (i32 i = 1; i <= n; ++i) {
        i32 f = find(i);
        printf("%d ", vis[f] ? vis[f] : (vis[f] = res++));
    }
    puts("");
    return 0;
}