竞极 Ace

最长公共子序列

最长公共子序列

题意

给定长度分别为 nn、mm 的两个整数序列 aa、bb，求它们的最长公共子序列的长度。

与上一题不同，子序列可以不连续，但元素的先后顺序不能改变。

例如：

a：1 2 3
b：1 9 2 9 3

最长公共子序列为 1 2 3，长度为 33；而最长相同子段的长度只有 11。

状态与转移

因为允许跳过元素，不必要求选出的序列以当前位置结尾。这次改用两个前缀中的最优值定义状态。

设 dp[i][j]dp[i][j] 表示 aa 的前 ii 个数与 bb 的前 jj 个数的最长公共子序列长度。

考虑两个前缀的最后一个元素：

  • 若 a[i]=b[j]a[i]=b[j]，可以将它们作为最后一对匹配，接在前面的最长公共子序列后面，得到 dp[i−1][j−1]+1dp[i-1][j-1]+1。
  • 若 a[i]≠b[j]a[i]\ne b[j]，这两个位置不可能同时被选中，至少需要跳过一个：跳过 a[i]a[i]，得到 dp[i−1][j]dp[i-1][j]；跳过 b[j]b[j]，得到 dp[i][j−1]dp[i][j-1]，取较大值。
$$dp[i][j]= \begin{cases} dp[i-1][j-1]+1, & a[i]=b[j],\\ \max(dp[i-1][j],\ dp[i][j-1]), & a[i]\ne b[j]. \end{cases}$$

初始化 dp[i][0]=dp[0][j]=0dp[i][0]=dp[0][j]=0，因为其中一个序列为空时，公共子序列长度为 00。答案直接取 dp[n][m]dp[n][m]。

参考代码

输入第一行为 n,mn,m，接下来两行分别为序列 aa、bb；输出最长公共子序列的长度。约定 1≤n,m≤20001\le n,m\le2000，∣a[i]∣,∣b[j]∣≤109|a[i]|,|b[j]|\le10^9。

#include <iostream>
#include <algorithm>
using namespace std;

const int N = 2005;
int n, m, a[N], b[N], dp[N][N];

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

    cin >> n >> m;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    for (int j = 1; j <= m; ++j) cin >> b[j];

    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            if (a[i] == b[j]) dp[i][j] = dp[i - 1][j - 1] + 1;
            else dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
        }
    }

    cout << dp[n][m] << '\n';
    return 0;
}

全局数组默认初始化为 00。时间复杂度 O(nm)O(nm)，空间复杂度 O(nm)O(nm)。

位运算优化

位序约定：图中按二进制顺序书写

为了避免在序列下标和二进制位之间反复转换，从这里开始，所有位集和差分的图都按二进制的书写顺序展示：

左边是高位                         右边是低位
a[n]  a[n-1]  ...  a[2]  a[1]

也就是说，图中的序列是倒着写的，最右边的有效位对应 a[1]。代码中第 j 位对应 a[j]，第 0 位空着不用。后面的图省略这个恒为 0 的空位，因此：

  • d << 1 把 a[j] 的位移到 a[j+1]，图上向左移动；
  • “最早出现的位置”是下标最小的位置，在图上表现为候选中的最右侧位置；
  • 二进制减法保留的是每段最低位的 1，正好就是每段最早出现的位置。

本节的 DP 行、差分和位运算示例均按这个方向展示。

1. 优化目标：从逐个状态转移到整行转移

为与代码一致，本节固定序列 aa，依次处理 b[i]b[i]。记 dp[i][j]dp[i][j] 为 bb 的前 ii 个元素与 aa 的前 jj 个元素的 LCS 长度。

普通做法枚举两个序列的前缀长度 i,ji,j，逐个计算 dp[i][j]dp[i][j]，时间复杂度为 O(nm)O(nm)。当 n,mn,m 都接近 7000070000 时，需要计算约 4949 亿个状态，无法满足本题时限。

固定 ii，观察同一行相邻两列：dp[i][j]dp[i][j] 相比 dp[i][j−1]dp[i][j-1] 只多考虑了 a[j]a[j] 一个元素，答案不会减小，且最多增加 11。因此：

dp[i][j]−dp[i][j−1]∈{0,1}.dp[i][j]-dp[i][j-1]\in\{0,1\}.

这使我们可以用一个 0101 数组保存当前行的差分：

d[j]=dp[i][j]−dp[i][j−1],1≤j≤n.d[j]=dp[i][j]-dp[i][j-1],\qquad 1\le j\le n.

接下来仍依次枚举 ii，但只维护当前行的差分数组 dd。我们的目标是：已知第 ii 行的差分，在处理 b[i+1]b[i+1] 时，通过位运算批量算出第 i+1i+1 行的差分。

第 i 行的差分 d + b[i+1] 在 a 中的所有匹配位置
                         ↓ 位运算批量更新
                    第 i+1 行的差分

初始 i=0i=0，差分全为 00。依次处理 b[1],b[2],…,b[m]b[1],b[2],\ldots,b[m]，每轮更新一次差分。

由于 dp[i][0]=0dp[i][0]=0，差分之和就是这一行最后一列的值。因此，处理完 b[m]b[m] 后，dd 中 11 的个数就是答案。

2. 用同一个例子观察相邻两行

两个序列为（这里仅列出原始序列，后面的图统一倒序展示）：

a：3 2 3 3 5 9 3 3
b：2 5 3

假设已经处理完 bb 的前两个元素 2 5，也就是 i=2i=2。当前 DP 行及其差分为：

a 的位置（高位到低位）：     8 7 6 5 4 3 2 1
a[j]：                   3 3 9 5 3 3 2 3
dp[2][j]：               2 2 2 2 1 1 1 0
差分 d：                  0 0 0 1 0 0 1 0

这里，位置 22 的 11 表示 LCS 长度第一次达到 11；位置 55 的 11 表示 LCS 长度第一次达到 22。

下一轮处理 b[3]=3b[3]=3，计算考虑前缀 2 5 3 的第 33 行：

dp[3][j]：   3 3 2 2 2 2 1 1
新的差分：    0 1 0 0 0 1 0 1

这一轮发生了三处变化：

  • 长度 11：原来最早在位置 22 出现，现在位置 11 的 3 就能与 b[3]b[3] 匹配，第一个 11 从位置 22 移到位置 11。
  • 长度 22：原来最早在位置 55 出现，现在前缀 3 2 3 已经能匹配 2 3，第二个 11 从位置 55 移到位置 33。
  • 长度 33：现在能匹配 2 5 3，在位置 77 新增一个 11，答案由 22 增加到 33。

下面研究怎样直接更新差分。

3. 差分的变化：每段只保留最右侧的候选

按下标从小到大看，旧差分中的每个 11 是一段的末端，最后一个 11 后面的 00 构成最后一段。为了遵守位序约定，下面把这些段整体倒序显示：

位置（高位到低位）：   8 7 6 | 5 4 3 | 2 1
旧差分 d：           0 0 0 | 1 0 0 | 1 0

这里的分段仍按下标区间理解，只是图中倒序书写。因此，旧差分中的 11 出现在每段的左端；它表示某种长度最早出现的位置。处理当前元素后，如果本段有更小下标的匹配位置，就把这个 11 移到候选中最右侧的位置；否则保留原来的 11。

本例处理 b[3]=3b[3]=3：

  • 左侧全 00 段 [6,8] 在图中写成 8 7 6：位置 7,87,8 都匹配，选择下标最小的 77，将 000 改为 010。因此最长长度增加 11。
  • 中间段 [3,5] 在图中写成 5 4 3：位置 3,43,4 都匹配，选择下标最小的 33，将 100 改为 001。
  • 右侧段 [1,2] 在图中写成 2 1：位置 11 匹配，将 10 改为 01。

第二段为什么这样变化？旧行中，长度 11 最早在位置 22 出现。把当前的 b[3]=3b[3]=3 接在旧方案 2 后面，从位置 33 起就能匹配 2 3，无需等到旧方案 2 5 的结束位置 55。

如果处理 b[i+1]b[i+1] 后，最长公共子序列的长度从 LL 增加到 L+1L+1，那么旧差分最后一个 11 后面的连续 00 中，一定恰有一个变成 11。 这里“后面”指下标更大的方向，在倒序图中位于最后一个 11 的左侧。新的匹配必须出现在这个连续 00 段中，才能得到长度 L+1L+1；选择其中下标最小、也就是图中最右侧的匹配位置，作为新增的 11。如果没有匹配，最长长度就不会增加。

按下标顺序看，区间 [1,2] 和 [3,5] 分别调整长度 11 和长度 22 最早出现的位置，末尾的全 00 段 [6,8] 负责尝试得到长度 33。这些变化都根据旧行计算；本轮前移的 11 不能再次用于匹配同一个 b[3]b[3]。

因此，只需把“旧差分中的 11”和“当前元素的匹配位置”都标成候选，然后每段保留下标最小、也就是图中最右侧的候选。

预处理位集 pos[v]，用 11 标记 aa 中所有等于 vv 的位置。本例为：

a（高位到低位）： 3 3 9 | 5 3 3 | 2 3
位置：             8 7 6 | 5 4 3 | 2 1
旧差分 d：         0 0 0 | 1 0 0 | 1 0
pos[3]：           1 1 0 | 0 1 1 | 1 0
候选 x：           1 1 0 | 1 1 1 | 1 1
新差分：           0 1 0 | 0 0 1 | 0 1

这里的“候选”指这一段的新 11 可以出现的位置。原有的 11 也要保留为候选，因为新增元素后，旧方案仍然有效；找不到更早的匹配位置时，就保留原来的 11。

候选位集通过按位或得到：

x = d | pos[b[i+1]]

pos 只需遍历一次 aa 来建立。之后每轮直接取出当前元素的匹配位集，无需再逐个比较所有 a[j]a[j]。

4. 用二进制减法找到每段最低位的 1

按照前面的约定，所有二进制行都从高位到低位书写，右侧对应较小的下标。下面不再把同一行翻来翻去。

先看单独一段。一个非零二进制数减去 11 时，最低的 11 变为 00，它右边的 00 都变为 11，更高位不变：

x：              11100
x-1：            11011
x ^ (x-1)：      00111
x & (x^(x-1))：  00100

先异或标出发生变化的位置，再与上原来的 x，就只保留了最低的那个 11。在图中它是候选中的最右侧位置，也就是下标最小的候选。

现在有多段，就在每段起点都放一个 11，作为减数。起点是位置 11，以及旧差分中每个 11 的后一位：

位置（高位到低位）：   8 7 6 | 5 4 3 | 2 1
旧差分 d：           0 0 0 | 1 0 0 | 1 0
起点 y：             0 0 1 | 0 0 1 | 0 1

把旧差分左移一位，再将第 11 位设为 11（第 00 位空着不用），即可得到 y。在图中，左移就是向左移动：从 a[j]a[j] 移到 a[j+1]a[j+1]。

接着计算 z=x-y，相当于每段都减去一个 11。除图中最左侧的全 00 段外，每段最高位都有旧差分留下的 11，足以承担借位，所以不会跨段借位；全 00 段若没有候选，最终也不会选出任何位置。

本例的完整运算为：

a 的位置（高位到低位）：   8 7 6 | 5 4 3 | 2 1
x：                     1 1 0 | 1 1 1 | 1 1
y：                     0 0 1 | 0 0 1 | 0 1
z=x-y：                 1 0 1 | 1 1 0 | 1 0
x ^ z：                 0 1 1 | 0 0 1 | 0 1
x & (x^z)：             0 1 0 | 0 0 1 | 0 1

得到的新差分为 0 1 0 | 0 0 1 | 0 1，与前面的手算结果一致。

于是，整行更新可以写成下面的位集运算。这里是算法表达式，具体的跨块移位和减法由后面的代码实现：

x = d | pos[b[i+1]]
y = (d << 1) | 2
z = x - y
d = x & (x ^ z)

其中 x & (x ^ z) 也等于 x & ~z，下面代码使用前一种写法。

5. 用 64 位整数分块实现

这里用 unsigned long long 保存位集，每个整数保存 6464 位，直接完成移位、按位或及减法。

第 jj 位对应 a[j]，第 00 位空着不用。块编号从 00 开始：

第 0 块：第   0～ 63 位
第 1 块：第   64～127 位
第 2 块：第   128～191 位
……

所以预处理匹配位置可以写成：

pos[a[i]][i / 64] |= 1ULL << (i % 64);

i / 64 表示块编号，i % 64 表示块内位置；1ULL << k 生成只有第 kk 位为 11 的数，|= 将这一位标记为 11，保留已有标记。

代码中的三个数组对应前面的公式：

数组 含义
f 起初保存旧差分，合并匹配位置后暂存 x，最后更新为新差分
g 每段起点的标记，对应 y
h 分块减法的结果，对应 x-y

每轮依次完成四步：

  1. 构造 g：将旧 f 左移。当前块最高位移出后，补到下一块最低位：

    g[j] |= f[j] << 1;
g[j + 1] |= f[j] >> 63;

    然后 g[0] |= 2，把第 11 位设为 11，标记第一段的起点。因为第 00 位不用，这里应写 2。

  2. 构造候选集合：f[j] |= pos[b[i]][j]，把旧差分和匹配位置合并，此时 f 暂存 x。

  3. 计算减法：从低位块到高位块计算 h[j] = f[j] - g[j] - borrow，其中 borrow 是上一块传来的借位。减去借位时不够减，或接着减 g[j] 时不够减，都需要向下一块借位。

  4. 得到新差分：f[j] &= f[j] ^ h[j]，每段只留下最低位的 11。

这些操作按块批量完成，不需要枚举每一段。按实际长度处理时，每轮需要 ⌊n/64⌋+1\lfloor n/64\rfloor+1 块；下面代码为了统一边界，固定处理 B = MAXN / 64 + 1 块，转移时间复杂度为 O(mB)O(mB)。当 n=m=70000n=m=70000 时，每轮 10941094 块，共约 76607660 万次块更新，每次更新包含固定数量的操作。

6. 参考代码

下面按 1≤n,m,a[i],b[i]≤700001\le n,m,a[i],b[i]\le70000 编写。pos 记录 aa 中的匹配位置，外层依次处理 b[i]，与前面的推导一致。g 每轮清零，因为移位结果使用 |= 合并；h 每个块都会重新赋值，无需清零。

#include <cstdio>
#include <cstring>
using namespace std;

const int MAXN = 70000;
const int B = MAXN / 64 + 1;

int n, m;
int a[MAXN + 5], b[MAXN + 5];
unsigned long long pos[MAXN + 5][B];
unsigned long long f[B + 1], g[B + 1], h[B + 1];

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
    for (int i = 1; i <= m; ++i) scanf("%d", &b[i]);

    // 第 i 位对应 a[i]，第 0 位空着不用
    for (int i = 1; i <= n; ++i) pos[a[i]][i / 64] |= 1ULL << (i % 64);
    
    for (int i = 1; i <= m; ++i) {
        memset(g, 0, sizeof(g));

        // g 保存每段起点：旧差分左移一位，再标记第 1 位
        for (int j = 0; j < B; ++j) {
            g[j] |= f[j] << 1;
            g[j + 1] |= f[j] >> 63;
        }
        g[0] |= 2;

        // f 暂存候选集合 x
        for (int j = 0; j < B; ++j) f[j] |= pos[b[i]][j];
       
        // h = x - g，从低位块到高位块处理借位
        unsigned long long borrow = 0;
        for (int j = 0; j < B; ++j) {
            h[j] = f[j] - g[j] - borrow;
            borrow = (borrow && f[j] == 0)
                   || (f[j] - borrow < g[j]);
        }

        // 每段只保留最低位的 1，得到新差分
        for (int j = 0; j < B; ++j) 	f[j] &= f[j] ^ h[j];
    }

    int ans = 0;
    for (int j = 0; j < B; ++j) ans += __builtin_popcountll(f[j]);
    printf("%d\n", ans);
    return 0;
}

与最大相同子段的区别

比较项 最大相同子段 最长公共子序列
连续性 必须连续 可以不连续
状态含义 以 a[i]a[i]、b[j]b[j] 结尾的最优值 两个前缀中的最优值
不匹配时 归零 跳过一个元素，取较大值
最终答案 所有 dp[i][j]dp[i][j] 的最大值 dp[n][m]dp[n][m]

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

题目描述

给定两个长度均为 nn 的排列 aa 和 bb，每个排列都恰好包含 1∼n1\sim n 中的每个整数一次。求它们的最长公共子序列的长度。

子序列是从原序列中删除若干元素（也可以不删除）后得到的序列，保留的元素相对顺序不变，位置可以不连续。公共子序列指同时是 aa 和 bb 的子序列。

输入格式

第一行一个整数 nn。

第二行 nn 个整数，表示排列 aa。

第三行 nn 个整数，表示排列 bb。

输出格式

输出一个整数，表示最长公共子序列的长度。

数据范围

1≤n≤1051\le n\le 10^5，保证 aa 和 bb 均为 1∼n1\sim n 的排列。

样例输入

5
3 2 1 4 5
2 4 1 5 3

样例输出

3

样例说明

2 4 5 是两个排列的一个最长公共子序列，长度为 33。

思路：转化为最长上升子序列

普通 LCS 的 O(n2)O(n^2) 做法无法通过。由于每个数只出现一次，可以用 pos[x] 记录 xx 在 bb 中的位置，再将 a[i]a[i] 替换成 pos[a[i]]：

b：        2 4 1 5 3
位置：     1 2 3 4 5

a：        3 2 1 4 5
替换后：   5 1 3 2 4

按 aa 的顺序选择元素，要使它们在 bb 中也保持原顺序，对应的位置就必须严格递增。 因此，替换后序列的最长上升子序列长度，就是原问题的答案。

例如，位置序列中的 1 2 4 对应原数值 2 4 5，答案为 33。

沿用二分做法：dp[k] 表示长度为 kk 的上升子序列的最小结尾。每次用 lower_bound 找到第一个 ≥x\ge x 的位置并替换，超出当前长度则令 len++。

时间复杂度 O(nlog⁡n)O(n\log n)，空间复杂度 O(n)O(n)。

参考代码

#include <iostream>
#include <algorithm>
using namespace std;

const int N = 100005;

int n, p1[N], p2[N], pos[N], dp[N];

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];
        pos[p2[i]] = i;
    }

    int len = 0;
    for (int i = 1; i <= n; ++i) {
        int x = pos[p1[i]];
        int k = lower_bound(dp + 1, dp + len + 1, x) - dp;
        dp[k] = x;
        if (k > len) len = k;
    }

    cout << len << '\n';
    return 0;
}