题目大意

给定两种 1 \sim n 的排列 p,q，和一个正整数 k，你需要构造一个由小写字母组成的字符串 s，满足：

1. 字符串至少包含 k 种小写字母。
2. 按照 p,q 的值作为下标排列字符串 s，组成字符串 s1,s2，满足 s1,s2 中的字母单调不降。

思路

Update in 2024.10.11 简化了证明过程。

在这里提供一种特别简单的写法以及思路。

先说一个结论，若 x 这个数分别出现在 p,q 的 i,j 位置，且按照 p,q 排列后的字符串 s1,s2 单调不降，则一定会满足：

s1[i] = s1[i + 1] = \cdots = s1[j - 1] = s1[j] \\ s2[i] = s2[i + 1] = \cdots = s2[j - 1] = s2[j] \\ s1[i \ldots j] = s2[i \ldots j]

（这里以及后文钦定 i \leq j，其实 i \geq j 也是一样的。）

一种感性的证明

拿一种 p,q 举例：

6 2 3 1 8 4 5 7
6 2 1 4 8 3 5 7
（我们查找 3 的位置）
则 i = 3, j = 5

当 i \neq j 时，显然 p[i],q[j] 左右两边数的个数不同，所以一定存在另一个数对应的位置 i_1, j_1 满足 i \leq i_1 \wedge j_1 \leq j。

根据题目要求的单调不降性质，我们有：

s1[i] \leq s1[i + 1] \leq \cdots \leq s1[i_1 - 1] \leq s1[i_1] s2[j_1] \leq s2[j_1 + 1] \leq \cdots \leq s2[j - 1] \leq s2[j] s1[i_1] = s2[j_1] \wedge s1[i] = s2[j]

再由不等式的性质，我们便可以得到：

s1[i] = s1[i + 1] = \cdots = s1[i_1 - 1] = s1[i_1] s2[j_1] = s2[j_1 + 1] = \cdots = s2[j - 1] = s2[j]

同样地，因为一定存在两个数的对应位置分别满足 i_k \geq j \wedge j_k \leq j 和 j_k \leq i \wedge i_k \geq i，由上述推论可以再得到：

s1[i] = s1[i + 1] = \cdots = s1[j - 1] = s1[j] \\ s2[i] = s2[i + 1] = \cdots = s2[j - 1] = s2[j] \\ s1[i \ldots j] = s2[i \ldots j]

到此就证明了一开始的结论。

（因为本人能力有限，不清楚更严谨的证明过程，如果有更好的思路话也可以补充一下。）

具体的做法

那么知道了上述的结论，你可以尝试找到所有 x 在 p,q 中的不同位置，然后得到若干条等式链。

如果你整理这些等式链，你会发现原序列被这些相等关系拆成了若干条区间，每个区间里的字符都相等，而区间与区间之间的字符必须满足字母单调不降，于是就做完了。

由等式链的性质，你只需要扫一遍 p[i],q[i]，看看它们所对应的数分别出现在对方 q,p 的位置，不断对这个位置取个 \max，记为 j，当 i = j 时就说明这一段区间已经到了结尾，第 i + 1 位置开始的便是新的区间了。

求出了不同的区间后，怎么构造字符串和判断是否有解就不再赘述，看代码即可。

时间复杂度：O(n)。

参考代码

#include <iostream>
#include <algorithm>
#include <cstdlib>

const int N = 200000 + 10;
using namespace std;

int read() {
    int x = 0, k = 1; char c = getchar();
    while (c < '0' || c > '9') { if (c == '-') k = -1; c = getchar(); }
    while (c >= '0' && c <= '9') x = (x << 3) + (x << 1) + (c ^ 48), c = getchar();
    return  x * k;
}

int n, k;
int p[N], q[N], rkp[N], rkq[N];
int Rng[N], cnt;
char c[N];

signed main() {
    n = read(), k = read();
    for (int i = 1; i <= n; ++i) p[i] = read(), rkp[p[i]] = i;
    for (int i = 1; i <= n; ++i) q[i] = read(), rkq[q[i]] = i;
    for (int i = 1, j = 0; i <= n; ++i) {
        j = max(j, rkq[p[i]]);
        j = max(j, rkp[q[i]]);
        if (j == i) Rng[++cnt] = i;
    }

    if (cnt < k) printf("NO\n"), exit(0);

    printf("YES\n");
    for (int i = 1, j = 1; i <= n; ++i) {
        if (i > Rng[j]) ++j;
        c[p[i]] = 'a' + min(k, j) - 1;
    }

    printf("%s\n", c + 1);
    return 0;
}

顺着这个思路走，其实代码实现非常的简单，而且运行时间也比较快，大概只有 140ms 左右。