P4801. 脉冲同步

场次：2026年4月18日-开发岗 · 来源：CodeFun2000 P4801

题目描述

两座信号塔各自记录了一段脉冲信号，每段信号都是一个长度为 $n$ 的排列，即由 1 到 n 这 $n$ 个整数按某种顺序排列而成，每个整数恰好出现一次。工程师希望提取出两段信号中共同存在的最长脉冲序列，称为“同步序列”。若有多个长度相同的最长同步序列，则选择在字典序意义下最大的那一个，以便后续处理。

【排列】长度为 $n$ 的排列是指由 $1,2,\dots,n$ 每个整数恰好出现一次构成的序列。 【子序列】从一个序列中删除零个或多个元素（保持原有顺序）后得到的新序列。 【同步序列】若某个序列 $C$ 既是序列 $A$ 的子序列，也是序列 $B$ 的子序列，则称 $C$ 为 $A$ 与 $B$ 的一个同步序列。 【字典序比较】对于两个等长序列 $X$ 和 $Y$，找到最小的下标 $i$ 使得 $X_i \neq Y_i$：若 $X_i > Y_i$，则 $X$ 字典序大于 $Y$；若 $X_i < Y_i$，则 $X$ 字典序小于 $Y$；若所有位置均相等，则 $X$ 与 $Y$ 相等。

现在给定两段脉冲信号（排列），请你分别求出每一对信号中最长同步序列的长度，并输出字典序最大的那一条同步序列。

排列的长度 $n$ 满足 $2 \le n \le 2 \times 10^5$。测试数据的组数 $T$ 满足 $1 \le T \le 10^5$，且所有测试数据中 $n$ 的总和不超过 $2 \times 10^5$。

输入格式

第一行包含一个整数 $T$，表示测试数据的组数。 接下来每组数据由三行组成：

• 第一行包含一个整数 $n$，表示两段脉冲信号（排列）的长度。
• 第二行包含 $n$ 个整数，表示第一段脉冲信号（排列），包含 $1$ 到 $n$ 各恰好一次。
• 第三行包含 $n$ 个整数，表示第二段脉冲信号（排列），包含 $1$ 到 $n$ 各恰好一次。

输出格式

对于每组测试数据，分两行输出结果：

• 第一行输出一个整数 $k$，表示最长同步序列的长度。
• 第二行输出 $k$ 个整数，用空格分隔，表示字典序意义下最大的最长同步序列。

示例

示例 1

输入：

1
5
1 2 3 4 5
5 4 3 2 1

输出：

1
5

说明：

序列 $q$ 完全逆序，任何两个不同数字在 $p$ 中的顺序与在 $q$ 中的顺序无法同时保持递增，因此最长同步序列的长度只能为 1。在所有长度为 1 的同步序列中，字典序最大的是仅由数字 $5$ 构成的序列。

示例 2

输入：

1
6
1 3 2 4 6 5
1 2 3 4 5 6

输出：

4
1 3 4 6

说明：

$q$ 是升序排列，因此要求在 $p$ 中选出的子序列必须也是升序的。在 $p$ 中的升序子序列有 1 3 4 6、1 2 4 6、1 3 4 5 等，它们的最长长度均为 4。在长度为 4 的同步序列中，字典序最大的为 1 3 4 6（优先比较首位数字，其次比较第二位数字，以此类推；1 3 4 6 的首位与其余序列相同，第二位 3 大于 2，故胜出）。

示例 3

输入：

1
2
2 1
1 2

输出：

1
2

说明：

$n = 2$ 的最小边界情况。$p$ 为 2 1，$q$ 为 1 2，两排列的最长公共子序列长度仅为 1。在所有长度为 1 的同步序列中，字典序最大的是 2。