P11052 [IOI 2024] 象形文字序列

请在提交时不要引用 `hieroglyphs.h`。 请勿用 C++14 (GCC 9) 提交。

一个研究团队正在研究象形文字序列之间的相似性。他们将每个象形文字表示成一个非负整数。为了开展研究，他们采用了关于序列的如下概念。 对于一个给定的序列 $A$，某个序列 $S$ 被称为是 $A$ 的**子序列**，当且仅当 $S$ 能够通过移除 $A$ 中的某些（也可能零个）元素而得到。 下表给出了序列 $A = [3, 2, 1, 2]$ 的子序列的一部分例子。 | 子序列 | 由 $A$ 得到子序列的方式 | | ------------ | -------------------------------------------------------- | | [3, 2, 1, 2] | 不移除任何元素。 | | [2, 1, 2] | [~~3~~, 2, 1, 2] | | [3, 2, 2] | [3, 2, ~~1~~, 2] | | [3, 2] | [3, ~~2~~, ~~1~~, 2] 或者 [3, 2, ~~1~~, ~~2~~] | | [3] | [3, ~~2~~, ~~1~~, ~~2~~] | | [ ] | [~~3~~, ~~2~~, ~~1~~, ~~2~~] | 另一方面，$[3, 3]$ 或 $[1, 3]$ 不是 $A$ 的子序列。 考虑有两个象形文字序列 $A$ 和 $B$。某个序列 $S$ 被称为是 $A$ 和 $B$ 的**公共子序列**，当且仅当 $S$ 同时是 $A$ 和 $B$ 的子序列。此外，我们说某个序列 $U$ 是 $A$ 和 $B$ 的一个**最全公共子序列**，当且仅当如下两个条件成立： * $U$ 是 $A$ 和 $B$ 的一个公共子序列。 * $A$ 和 $B$ 的任意公共子序列，都是 $U$ 的一个子序列。 可以证明，任意两个序列 $A$ 和 $B$ 都至多有一个最全公共子序列。 研究人员发现了两个象形文字序列 $A$ 和 $B$。序列 $A$ 包含 $N$ 个象形文字，而序列 $B$ 包含 $M$ 个象形文字。请帮助研究人员为序列 $A$ 和 $B$ 找到一个最全公共子序列，或者判定这样的序列并不存在。

``` N M A[0] A[1] ... A[N-1] B[0] B[1] ... B[M-1] ```

``` T R[0] R[1] ... R[T-1] ``` 这里 $R$ 是 `ucs` 所返回的数组，而 $T$ 为其长度。

## 实现细节 你要实现以下函数。 ``` std::vector ucs(std::vector A, std::vector B) ``` * $A$：长度为 $N$ 的数组，给出第一个序列。 * $B$：长度为 $M$ 的数组，给出第二个序列。 * 如果 $A$ 和 $B$ 有一个最全公共子序列，该函数应当返回一个包含该序列的数组。否则，该函数应当返回 $[-1]$（一个长度为 $1$ 的数组，其唯一元素为 $-1$）。 * 对每个测试用例，该函数恰好被调用一次。 ## 约束条件 * $1 \leq N \leq 100\,000$ * $1 \leq M \leq 100\,000$ * 对所有满足 $0 \leq i < N$ 的 $i$，都有 $0 \leq A[i] \leq 200\,000$ * 对所有满足 $0 \leq j < M$ 的 $j$，都有 $0 \leq B[j] \leq 200\,000$ ## 子任务 | 子任务 | 分数 | 额外的约束条件 | | :-----: | :---: | ------------------------------------------------------------ | | 1 | $3$ | $N = M$；$A$ 和 $B$ 均由 $N$ 个**不同的**整数构成，取自 $0$ 到 $N-1$（包括这两个值） | | 2 | $15$ | 对任意整数 $k$，$k$ 在 $A$ 和 $B$ 中的出现次数，加起来至多等于 $3$。 | | 3 | $10$ | 对所有满足 $0 \leq i < N$ 的 $i$，都有 $A[i] \leq 1$；对所有满足 $0 \leq j < M$ 的 $j$，都有 $B[j] \leq 1$ | | 4 | $16$ | $A$ 和 $B$ 存在最全公共子序列。 | | 5 | $14$ | $N \leq 3000$；$M \leq 3000$ | | 6 | $42$ | 没有额外的约束条件。 | ## 例子 ### 例 1 考虑以下函数调用。 ``` ucs([0, 0, 1, 0, 1, 2], [2, 0, 1, 0, 2]) ``` 此时，$A$ 和 $B$ 的公共子序列为：$[\ ]$，$[0]$，$[1]$，$[2]$，$[0, 0]$，$[0, 1]$，$[0, 2]$，$[1, 0]$，$[1, 2]$，$[0, 0, 2]$，$[0, 1, 0]$，$[0, 1, 2]$，$[1, 0, 2]$ 和 $[0, 1, 0, 2]$。 由于 $[0, 1, 0, 2]$ 是 $A$ 和 $B$ 的一个公共子序列，而 $A$ 和 $B$ 的所有公共子序列又都是 $[0, 1, 0, 2]$ 的子序列，因此函数应该返回 $[0, 1, 0, 2]$。 ### 例 2 考虑以下函数调用。 ``` ucs([0, 0, 2], [1, 1]) ``` 此时，$A$ 和 $B$ 唯一的公共子序列为空序列 $[\ ]$。因此函数应该返回一个空数组 $[\ ]$。 ### 例 3 考虑以下函数调用。 ``` ucs([0, 1, 0], [1, 0, 1]) ``` 此时，$A$ 和 $B$ 的公共子序列为 $[\ ]$，$[0]$，$[1]$，$[0, 1]$ 和 $[1, 0]$，可以看出两者并不存在最全公共子序列。因此，函数应该返回 $[-1]$。