两个排列的最长公共子序列

形式化题目

给定 $1,2,\ldots,n$ 的两个排列 $P_1,P_2$ 。求最大的 $k$ ，使得存在两组严格递增下标

i_1<i_2<\cdots<i_k,\qquad j_1<j_2<\cdots<j_k

满足对每个 $t$ 都有 $P_1[i_t]=P_2[j_t]$ 。

解法路线

题面给了两份真实的数据范围，正好对应两层解法：

层次	约束	解法	复杂度
暴力	$n$ 很小	枚举 $P_1$ 的所有子序列，逐个检查	$O(2^n n)$
子任务	$n \le 10^3$	一般序列的二维 LCS DP	$O(n^2)$
正解（正式主解）	$n \le 10^5$	值 → $P_1$ 下标映射，转成 LIS	$O(n\log n)$

第一层说明"公共子序列"到底是什么，第二层给出对任意序列都成立的做法，第三层利用"两个串都是排列"这一额外条件把 $O(n^2)$ 压到 $O(n\log n)$ 。本文的正式主解是第三层，代码见 ## 正解。

正解有两种等价写法，正文都给出：

写法	保留的信息	二分条件	代码
`tail` 版本	只保留每个长度的最小结尾 `tail[len]`	第一个 $\ge x$ 的位置	`main2.cpp`
`c[]` / `f[]` 版本	额外保留每个元素的 LIS 值 `f[i]`	第一个 $> x$ 的位置	`main.cpp`

两种写法都用《二分查找》文章的 first_true 手写二分，不调用 lower_bound / upper_bound；它们对 LIS 的定义完全一致，main2.cpp 用的是 rbook 模板 lis-binary 的 tail 数组，main.cpp 用的是按元素记录 f[i] 的常见竞赛写法。本文与 rbook 的最长上升子序列一文中的"LCS 的排列优化"对应。

暴力解法

适用范围

$n$ 最多到 15 左右。它只是用来把"公共子序列"的定义变成可执行的程序。

思路

把"枚举 $P_1$ 的所有子序列"写成选择树： $P_1$ 的每个数只有选和不选两种决定， $n$ 个数一共产生 $2^n$ 条完整的 01 选择序列。用 choose[] 记录每层的选择，dfs(dep) 只负责决定第 dep 个数选不选，选中的数按原顺序放进 candidate：

dep > n 说明一条完整选择序列生成完毕，candidate 就是一个 $P_1$ 的子序列；
在叶子节点检查 candidate 是否是 $P_2$ 的子序列，是就更新答案。

检查同样用一个指针在 $P_2$ 上顺序扫描：扫完 $P_2$ 时指针走完了 candidate，就说明匹配成功。

先生成完整选择序列、再在叶子统一检查，逻辑最短，也最容易确认没有漏掉任何方案。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-09-19 18:44
 * update_at: 2026-09-19 18:44
 */
// brute.cpp：小数据暴力解，使用 01 序列 / 选择序列递归枚举 P1 的所有子序列。
// 每一层决定 P1 的第 dep 个数选或不选，选出来的数按原顺序放进 candidate；
// 到了叶子节点再检查 candidate 是否是 P2 的子序列，是就更新答案。
// n 到 15 左右就慢得明显，只用来对拍和理解题意。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 20;

int n;
int p1[MAXN], p2[MAXN];  // 两个排列，下标 1..n

int choose[MAXN];        // choose[i] 表示 P1 的第 i 个数选(1)还是不选(0)
int candidate[MAXN];     // 由 P1 中被选的数按原顺序拼成的子序列
int clen;                // candidate 的当前长度
int ans;                 // 目前找到的最长公共子序列长度

// 判断 candidate 是否是 P2 的子序列：在 P2 上顺序扫描，能依次匹配完就算成功。
bool is_subsequence_of_p2() {
    int pos = 1;
    for (int i = 1; i <= n && pos <= clen; i++) {
        if (p2[i] == candidate[pos]) pos++;
    }
    return pos > clen;
}

void dfs(int dep) {
    if (dep > n) {
        // 完整的选择序列已经生成，检查候选子序列并统计答案
        if (is_subsequence_of_p2()) {
            if (ans < clen) ans = clen;
        }
        return;
    }

    // 这一层选择 P1 的第 dep 个数：0 不选，1 选
    for (int i = 0; i <= 1; i++) {
        choose[dep] = i;
        if (i == 1) candidate[++clen] = p1[dep];
        dfs(dep + 1);
        if (i == 1) clen--;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    for (int i = 1; i <= n; i++) cin >> p1[i];
    for (int i = 1; i <= n; i++) cin >> p2[i];

    dfs(1);
    cout << ans << "\n";

    return 0;
}

复杂度与瓶颈

时间： $2^n$ 条选择序列，每条花 $O(n)$ 检查，总 $O(2^n n)$ 。
空间： $O(n)$ 。

瓶颈是枚举量 $2^n$ ，与 $P_1$ 的具体内容无关，换成枚举 $P_2$ 的子序列也一样。

子任务解法： $n \le 10^3$

适用范围

$n \le 10^3$ ，此时两张 $10^3\times10^3$ 的表规模可以接受。这个做法对任意两个序列都成立，不要求是排列。

思路

用前缀定义状态：

$$f(i,j)=\text{$ P_1$ 的前 $i$ 个数与 $P_2$ 的前 $j$ 个数的最长公共子序列长度}

边界 $f(i,0)=f(0,j)=0$ （有一边为空时只能取空串）。转移分两种情况：

若 $P_1[i]=P_2[j]$ ，这对相同的数可以直接接在 $f(i-1,j-1)$ 的公共子序列后面：

f(i,j)=f(i-1,j-1)+1

否则它们不可能同时是公共子序列的最后一个元素，至少丢掉一个：

f(i,j)=\max\bigl(f(i-1,j),\ f(i,j-1)\bigr)

答案即 $f(n,m)$ 。 $(n+1)(m+1)$ 个格子，每个 $O(1)$ 转移。

再回头看暴力为什么慢： $2^n$ 条选择序列里，"已经用掉 $P_1$ 的哪个前缀、 $P_2$ 的哪个前缀"这个信息被反复重算，而公共子序列的长度只由这两个前缀决定。DP 就是把这些方案按状态合并。

代码

与正解共用同一份代码文件 main.cpp，不单独给出：正解在本题的数据范围内已经完全覆盖这个做法（严格更快，且 $n\le10^3$ 时同样通过），单独再放一份 $O(n^2)$ 的 DP 只会重复同一套输入输出。需要对照时直接看 ## 正解 的代码，pos[] 换成二维 dp[][] 即可。

复杂度与瓶颈

时间： $O(n^2)$ ， $n=10^3$ 时 $10^6$ 次转移，可以通过。
空间： $O(n^2)$ （或只保留两行滚动， $O(n)$ ）。

瓶颈在状态数： $n=10^5$ 时是 $10^{10}$ 次转移，无论如何优化常数都过不去。注意转移里判断 $P_1[i]=P_2[j]$ 这件事本身是因为"同一个值可能在序列里出现多次"才需要的，而本题两个串都是排列，这个信息其实被浪费了。

正解

关键观察

问题？ "两个串都是排列"这个条件能给我们什么？

每个值在 $P_1$ 中只出现一次，在 $P_2$ 中也只出现一次。于是可以定义

\texttt{pos}[v]=v \text{ 在 } P_1 \text{ 中的下标}

这本身就是一张一一对应的表。

问题？ 用 pos 把 $P_2$ 的每个数换成它在 $P_1$ 里的位置，会得到什么？

得到一个位置序列 $S$ ： $S_i=\texttt{pos}[P_2[i]]$ 。举例， $P_1=(3,2,1,4,5)$ 、 $P_2=(1,2,3,4,5)$ 时：

	1	2	3	4	5
$P_1$	3	2	1	4	5
$P_2$	1	2	3	4	5
$\texttt{pos}[P_2[i]]$	3	2	1	4	5

问题？ 为什么公共子序列就等于 $S$ 的上升子序列？

两边各推一次。

设选出的公共子序列的值按在 $P_1$ 中的顺序是 $v_1,\dots,v_k$ 。因为它是 $P_1$ 的子序列， $\texttt{pos}[v_1]<\cdots<\texttt{pos}[v_k]$ ；又因为它是 $P_2$ 的子序列，这些值在 $P_2$ 里也按 $v_1,\dots,v_k$ 的顺序出现，所以它们在 $S$ 中对应位置的值是递增的，构成 $S$ 的一个上升子序列。
反过来，任取 $S$ 的一个上升子序列，取出对应位置的值。这些值在 $S$ 中的值序列递增，也就是它们在 $P_1$ 中的顺序与在 $P_2$ 中的顺序一致，因此同时是 $P_1$ 和 $P_2$ 的公共子序列。

两个方向的长度集合互相包含，最大值也相等。所以答案就是 $S$ 的最长严格上升子序列长度。

验证一下样例： $S=(3,2,1,4,5)$ ，最长的严格上升子序列是 $(1,4,5)$ 或 $(2,4,5)$ 或 $(3,4,5)$ ，长度 3，与样例输出一致，对应的公共子序列就是 $\{1,4,5\}$ （或 $\{2,4,5\}$ 、 $\{3,4,5\}$ ）。

问题？ 上升还是下降？

必须严格上升。若误用下降子序列会算错： $P_1=(2,1),P_2=(1,2)$ 时 $S=(2,1)$ ，下降子序列长度 2，但两个排列真正的公共子序列最长只有 1。

问题？ 怎么在 $O(n\log n)$ 内求 LIS？

维护数组 tail：

tail[len] = 长度为 len 的严格上升子序列中，末尾元素的最小可能值。

它天然单调不减：长度越长，结尾不可能更小（更长的子序列的前缀也是子序列，所以长度 len 的结尾不可能小于长度 len-1 的结尾的最小值）。于是依次处理每个 $x$ ，二分找到第一个 $\ge x$ 的位置 $p$ ：

找不到（ $p$ 落在虚拟位置）： $x$ 比所有结尾都大，可以接在当前最长的上升子序列后面，追加，长度加一；
找到了：用 $x$ 覆盖 tail[p]，让长度为 $p$ 的子序列结尾变小，为后面留余地，长度不变。

处理完毕，len 就是 LIS 长度。

问题？ 这个二分怎么手写？

它恰好是 rbook《二分查找》文章里 first_true 模板的形状：在有效区间上，check(p) = (tail[p] >= x) 随着 $p$ 增大从 false 变成 true，答案就是第一个 true。把区间取成 [1, len+1]，位置 len+1 当作虚拟位置（表示"没有满足条件的元素"），就能保证答案总是落在区间内，不必额外判断越界：

cpp

1
2
3
4
5while (l < r) {
    int mid = l + (r - l) / 2;
    if (tail[mid] >= x) r = mid;
    else l = mid + 1;
}

mid = l + (r-l)/2 在 l < r 时恒有 mid < r，所以 mid 只会落在 1..len 的真实位置上，不会读到 tail[len+1] 的旧值。循环结束时 $l=r$ ，就是第一个 $\ge x$ 的位置；若它等于 len+1，说明 $x$ 比所有结尾都大，要追加。这里用的是 >=，对应严格上升子序列；若题目要求非下降子序列，把条件改成 tail[mid] > x。

问题？ 为什么 tail[p] = x; 可以直接写，而不是 tail[p] = min(tail[p], x);？

因为替换动作的语义和二分找出来的位置两者合起来已经保证了 tail[p] >= x，此时 min(tail[p], x) 恒等于 x，赋值就是最小值，不需要再比较：

替换的语义是"让该长度的结尾更小"。tail 维护的是最小值，按定义更新应该是
cpp
```
1tail[p] = min(tail[p], x);
```
二分第一个 $\ge x$ 的位置，意味着 $p$ 满足两边夹：左侧所有位置都 $< x$ ，而 tail[p] >= x。
两者相减：在这个位置上 min(tail[p], x) == x，所以直接赋值与取 min 完全等价。

换一个说法： $x$ 接不上长度 $p$ 的子序列（那需要 tail[p] < x），它只能接在长度 $p$ 的子序列前面，于是为长度 $p$ 贡献了一个更小的结尾——把 tail[p] 改小正是在描述这件事。

反过来看，如果真出现 tail[p] < x 却还去赋值，那就是把最小值改大了，tail 的单调性与"最小结尾"这两个不变量同时被破坏，后面必然算错。所以"能不能省掉 min"完全等价于"二分找的是不是第一个 $\ge x$ "，两者是同一件事的两种说法。

注意追加分支不能沿用这个推理：此时 p 落在虚拟位置，tail[p] 根本不是有效数据，没有大小可比较，唯一正确的动作是长度加一后写入。下面 main2.cpp 里把它显式写成两行就是为了避免这种误读。

代码

两份代码做的是同一件事，差别只在 LIS 部分保留了哪些信息。

写法一（main2.cpp）：只维护 tail，不记录 f[i]

数组从下标 1 开始：tail[len] 是长度为 len 的最小结尾，len 是当前 LIS 长度。每个 $x$ 二分第一个 $\ge x$ 的位置 $p$ ，替换或追加。

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75/*
 * Author by Rainboy blog: https://rainboylv.com github:
 * https://github.com/rainboylvx rbook: -> https://rbook.roj.ac.cn
 * https://rbook2.roj.ac.cn rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-09-19 18:44
 * update_at: 2026-09-19 18:44
 */
// main2.cpp：两个排列的最长公共子序列（只维护 tail 的写法）。
//
// 建模：把 P1 的每个值映射成它在 P1 中的下标 pos[v]，
// 再把 P2 的每个值换成 pos[P2[i]]，得到一个下标序列 a[]。
// P1 与 P2 的公共子序列 <-> a[] 的严格上升子序列，
// 所以答案就是 a[] 的 LIS 长度。
//
// LIS 写法：
//   tail[len] = 长度为 len 的严格上升子序列中，末尾元素的最小可能值
//   对每个 x，二分找 tail 中第一个 >= x 的位置 p：
//     - 找到：tail[p] = x（让长度为 p 的子序列结尾更小）
//     - 找不到（p 落在虚拟位置 len+1）：长度加一后追加
// 二分是手写的，来自 rbook《二分查找》文章的 first_true 模板，
// 不调用 lower_bound。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100005;

int n;
int pos[MAXN];  // pos[v] = 值 v 在排列 P1 中的下标（1-based）
int tail[MAXN]; // tail[len] = 长度为 len 的上升子序列中，末尾下标的最小值
int len;        // tail 的有效长度，也是当前的 LIS 长度

// 在 tail[l..r] 中查找第一个满足 tail[mid] >= x 的位置。
// tail[1..len] 单调不减，check(mid) 形如 false false ... false true true ... true。
// 区间取 [1, len+1]，位置 len+1 是虚拟位置，表示“不存在 >= x 的元素”。
int first_true(int l, int r, int x) {
    while (l < r) {
        int mid = l + (r - l) / 2;
        if (tail[mid] >= x) r = mid;
        else l = mid + 1;
    }
    return l;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;

    for (int i = 1; i <= n; i++) {
        int v;
        cin >> v;
        pos[v] = i;  // 记下每个值在 P1 中的位置
    }

    for (int i = 1; i <= n; i++) {
        int v;
        cin >> v;
        int x = pos[v];  // 把 P2 中的值换成它在 P1 中的位置

        // p 是 tail[1..len] 中第一个 >= x 的位置；找不到就是虚拟位置 len+1
        int p = first_true(1, len + 1, x);

        if (p == len + 1) {  // 没找到说明 x 能接在最长的后面，长度加一
            len++;
            tail[len] = x;
        } else {
            tail[p] = x;  // 找到就替换（让该长度的结尾尽量小）
        }
    }

    cout << len << "\n";

    return 0;
}

写法二（main.cpp）：额外记录每个元素的 LIS 值 f[i]

text

1
2
3c[j] = 当前所有 lis 值等于 j 的元素中，值最小的那个
f[i] = 以第 i 个元素结尾的 lis 值
     = 第一个满足 c[j] > a[i] 的下标 j

因为 f[i] 就是 $x$ 能接上的长度，所以答案要取所有 f[i] 的最大值，而不是数组长度。这里二分的条件是 c[mid] > x（第一个大于），a[i] 相等时也能接在长度 $j$ 后面，同样对应严格上升；更新写成 c[f[i]] = min(c[f[i]], a[i])，让代码与 c[j] 的"最小值"定义逐字对应。

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-09-19 18:44
 * update_at: 2026-09-19 18:44
 */
// main.cpp：两个排列的最长公共子序列。
//
// 建模：把 P1 的每个值映射成它在 P1 中出现的下标 pos[v]，
// 再把 P2 的每个值换成 pos[P2[i]]，得到一个下标序列 a[]。
// P1 与 P2 的公共子序列 <-> a[] 的严格上升子序列，
// 所以答案就是 a[] 的 LIS 长度。
//
// LIS 写法：
//   c[j] = 当前所有 lis 值等于 j 的元素中，a 值最小的那个
//   f[i] = 以第 i 个元素结尾的 lis 值
//         = 第一个满足 c[j] > a[i] 的下标 j（a[i] 相等时能接到长度 j 后面，
//           所以要用 >，不能用 >=，对应严格上升）
//   c[f[i]] = min(c[f[i]], a[i])
// c[] 单调不减，所以"第一个大于 a[i] 的位置"用手写二分找，
// 模板来自 rbook《二分查找》文章的 first_true，不调用 upper_bound。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e6+5; //数组的最大长度

int n;        //排列的长度
int a[maxn];  //把 P2 的值换成它在 P1 中的下标之后得到的序列
int pos[maxn];//pos[v] = 值 v 在排列 P1 中的位置
int c[maxn];  //c[j]表示: 所有 lis值 == j 那些元素中, 值最小的那个
int f[maxn];  //f[i] = 第 i 个元素(即 a[i]) 的 lis 值

//手写二分: 在 c[l..r] 中查找第一个满足 c[mid] > x 的位置。
//c[] 单调不减，check(mid) 形如 false false ... false true true ... true。
//区间右端传 n+1，位置 n+1 是虚拟位置(c[n+1] 是哨兵无穷大)，表示"不存在 > x 的元素"。
int first_greater(int l, int r, int x){
    while(l < r){
        int mid = l + (r - l) / 2;
        if(c[mid] > x) r = mid;      //答案在左半边(或就是 mid)
        else l = mid + 1;            //c[mid] <= x, mid 及左边都不可能是答案
    }
    return l;
}

//求 a[1..n] 的 LIS: c 与 f 的含义见上面的注释
void lis(){
    memset(c,0x7f,sizeof(c)); //先全部置成无穷大, 表示还没有 lis值==j 的元素
    //虚拟位置 n+1 也是无穷大, 用它兜底, 保证一定找得到一个 > a[i] 的位置;
    //由于 a[i] <= n < c[n+1], 二分永远不会真的返回 n+1
    f[1] = 1;                 //第一个元素自己就构成长度 1 的上升子序列
    c[1] = a[1];
    for(int i=2;i<=n;++i){
        f[i] = first_greater(1, n+1, a[i]); //a[i] 的 lis值
        c[f[i]] = min(c[f[i]],a[i]);        //lis值相同的元素里, 只保留值最小的
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    //第一行: 排列 P1, 记下每个值在 P1 中出现的位置
    for(int i=1;i<=n;++i){
        int v;
        cin >> v;
        pos[v] = i;
    }
    //第二行: 排列 P2, 把每个值换成它在 P1 中的位置, 得到序列 a
    for(int i=1;i<=n;++i){
        int v;
        cin >> v;
        a[i] = pos[v];
    }

    lis();

    //答案就是整个序列里最大的 lis值
    int ans = 0;
    for(int i=1;i<=n;++i){
        ans = max(ans, f[i]);
    }
    cout << ans << "\n";
    return 0;
}

复杂度

时间：读入与映射 $O(n)$ ， $n$ 次二分各 $O(\log n)$ ，总 $O(n\log n)$ 。两份代码完全一样。
空间：pos[] 加 LIS 用的数组，各 $O(n)$ ；main.cpp 还多一个 f[]，量级不变。

总结

核心观察：两个串是排列 ⟹ 值到 $P_1$ 的下标是一一对应的 ⟹ 把 $P_2$ 的每个值换成它在 $P_1$ 中的位置后，“公共子序列"就退化成"位置序列的严格上升子序列”。
为什么能降复杂度：一般 LCS 需要 $O(nm)$ 是因为同一个值可能出现多次，必须逐位置比较；排列题里重复性消失，这个比较被一张 $O(1)$ 查表的 pos 取代，问题随即变成 LIS。
LIS 的二分实现：tail[len] 表示长度为 len 的上升子序列的最小结尾，对每个 $x$ 用「二分第一个 $\ge x$ 的位置」替换或追加，len 即答案。二分可以手写成 first_true 模板（区间 $[1,len+1]$ ，len+1 是虚拟位置），严格上升用 tail[mid] >= x，非下降用 tail[mid] > x，不必区分 lower_bound 与 upper_bound。
为什么 tail[p] = x 不用写 min：二分第一个 $\ge x$ 的位置保证了 tail[p] >= x，而替换的语义本就是"让该长度的结尾更小"，此时 min(tail[p], x) 恒等于 $x$ 。反过来说，若 tail[p] < x 还去赋值，就把最小值改大了——所以"能省 min"与"二分找第一个 $\ge x$ "是同一件事；追加分支没有可比的大小，只能长度加一后写入。
两种等价写法：只维护 tail 时答案就是 len；额外记录 f[i] 时答案取 $\max_i f[i]$ ，后者多一层信息，方便回答"以第 $i$ 个数结尾的最长上升子序列有多长"。
易错点：把排列条件丢掉就不成立（值重复时映射不再一一对应）；求 LIS 时误用非严格比较会多算； $S$ 是"位置序列"，不能反过来对 $P_1$ 求下降子序列。