01 | 笔试算法题：最长且字典序最大的公共子序列
题目：
给定两个长度为 n 的数组 A、B，二者都是 1..n 的排列。
要求找到一个公共子序列：
- 长度尽可能长；
- 在所有最长公共子序列中，字典序尽可能大。
基本认识：假如是公共子序列，那么在 A 数组和 B 数组中的下标相对位置应该是一样的
然后 dp 一维数组的含义：dp[i] 代表以 A[i] 为公共子序列的第一个数字的话能够得到的最大的长度
变量声明：posA 保存数字到A数组下标的映射，posB 保存数字到B数组下标的映射
dp[i] 的更新问题：从右向左遍历 i，同时找到一个j, 如果 i < j 且 posB[A[i]] < posB[A[j]] 那么 dp[i] = dp[j] + 1
dp 数组更新的过程中发现，我们需要快速找到一个 max(dp[j])。引入一个线段树，线段树保存的是 B 数组中 以[posB[A[i]] + 1, n ) 区间内的数字 和 A 数组可以形成的最长子序列。
最难理解的就是这个一维数组维护的是什么。它维护的是在动态遍历 i 的情况下，B 数组能够提供的最长公共子序列的长度
点击查看代码
/*
题目：
给定两个长度为 n 的数组 A、B，二者都是 1..n 的排列。
要求找到一个公共子序列：
1. 长度尽可能长；
2. 在所有最长公共子序列中，字典序尽可能大。关键观察：
因为 A、B 都是排列，每个数字只出现一次。
如果我们知道某个值 x 在 B 中的位置 posB[x]，
那么 A 中的一个子序列 A[i1], A[i2], ...
想要同时也是 B 的子序列，就必须满足：i1 < i2 < ...
并且posB[A[i1]] < posB[A[i2]] < ...也就是说，本题等价于：
在 A 的顺序中，找一个子序列，使这些元素在 B 中的位置也递增。
*//*
一维 Fenwick Tree / Binary Indexed Tree。这里维护的是“前缀最大值”，不是常见的前缀和。
update(i, v)：把位置 i 的最大值更新为 max(原值, v)
query(i)：查询区间 [1, i] 的最大值
*/
struct FenwickMax {int n;vector<int> tree;FenwickMax(int n = 0) : n(n), tree(n + 1, 0) {}void update(int i, int value) {while (i <= n) {tree[i] = max(tree[i], value);i += i & -i;}}int query(int i) const {int ans = 0;while (i > 0) {ans = max(ans, tree[i]);i -= i & -i;}return ans;}
};/*
二维 Fenwick Tree。用途：
在贪心构造答案时，我们需要快速查询：当前剩余长度为 need 时，在 A 的下标 > lastA 且 B 的下标 > lastB 的所有候选位置中，最大的数字是多少。也就是一个二维后缀矩形查询：i > lastA 且 posB[A[i]] > lastBFenwick Tree 天然适合前缀查询，所以这里做坐标反转：x = n - i + 1y = n - posB[A[i]] + 1那么条件：i > lastA
等价于：x <= n - lastA条件：posB[A[i]] > lastB
等价于：y <= n - lastB于是二维后缀查询就变成了二维前缀查询：x <= maxX 且 y <= maxY二维 Fenwick 直接开 n*n 会太大。
这里使用“树状数组套离散化树状数组”：
1. 预处理每个外层 Fenwick 节点可能出现的 y 坐标；
2. 每个外层节点只开自己需要的内层数组。
*/
struct Fenwick2DMax {int n;vector<vector<int>> ys;vector<vector<int>> tree;Fenwick2DMax(int n, const vector<pair<int, int>>& points) : n(n) {ys.assign(n + 1, {});// 预处理：一个点 (x, y) 在 update(x, y, value) 时会影响哪些外层节点。for (auto [x, y] : points) {for (int i = x; i <= n; i += i & -i) {ys[i].push_back(y);}}tree.resize(n + 1);// 每个外层节点内部只保留它真正需要的 y 坐标。for (int i = 1; i <= n; i++) {sort(ys[i].begin(), ys[i].end());ys[i].erase(unique(ys[i].begin(), ys[i].end()), ys[i].end());tree[i].assign(ys[i].size() + 1, 0);}}// 在二维点 (x, y) 上插入一个候选值 value。void update(int x, int y, int value) {for (int i = x; i <= n; i += i & -i) {int j = lower_bound(ys[i].begin(), ys[i].end(), y) - ys[i].begin() + 1;while (j < (int)tree[i].size()) {tree[i][j] = max(tree[i][j], value);j += j & -j;}}}// 查询矩形 [1, x] * [1, y] 中出现过的最大 value。int query(int x, int y) const {int ans = 0;for (int i = x; i > 0; i -= i & -i) {// 当前外层节点里，找出所有 <= y 的离散坐标数量。int j = upper_bound(ys[i].begin(), ys[i].end(), y) - ys[i].begin();while (j > 0) {ans = max(ans, tree[i][j]);j -= j & -j;}}return ans;}
};int main() {ios::sync_with_stdio(false);cin.tie(nullptr);int n;cin >> n;vector<int> a(n + 1), b(n + 1);vector<int> posA(n + 1), posB(n + 1);for (int i = 1; i <= n; i++) {cin >> a[i];posA[a[i]] = i;}for (int i = 1; i <= n; i++) {cin >> b[i];posB[b[i]] = i;}/*step 1：计算 dp[i]dp[i] 表示：必须选择 a[i] 作为第一个元素时，从 i 开始最多还能构成多长的公共子序列。转移：dp[i] = 1 + max(dp[j])条件是：j > iposB[a[j]] > posB[a[i]]这就是按 i 从右往左扫，维护 posB 维度上的最大 dp。为了用 Fenwick 做“posB 更大”的后缀查询，再做一次坐标反转：c = n - posB[a[i]] + 1posB[a[j]] > posB[a[i]]等价于：c[j] < c[i]所以 query(c - 1) 就能查到所有合法后继的最大 dp。*/vector<int> dp(n + 1);FenwickMax bit(n);int longest = 0;for (int i = n; i >= 1; i--) {int reversedPosB = n - posB[a[i]] + 1; // 找到 a[i] 在 B 中的位置（改成前缀）dp[i] = bit.query(reversedPosB - 1) + 1;bit.update(reversedPosB, dp[i]); // 以 a[i] 开头的最长长度；以 reversedPosB 下标（在 B) 中的最长长度longest = max(longest, dp[i]);}/*step 2：按 dp 值分桶。构造答案时，如果当前还需要 need 个元素，那么当前位置必须选择一个 dp[i] >= need 的点。这里使用“逐层加入”的技巧：当 need 从 longest 降到 1 时，把 dp[i] == need 的点加入二维 Fenwick。因为 need 是递减的，所以加入过的数据会一直保留。查询时，二维 Fenwick 中包含的正是所有 dp[i] >= need 的点。*/vector<vector<int>> bucket(longest + 1);vector<pair<int, int>> allPoints;for (int i = 1; i <= n; i++) {bucket[dp[i]].push_back(i);int x = n - i + 1;int y = n - posB[a[i]] + 1;allPoints.push_back({x, y});}Fenwick2DMax bit2(n, allPoints);/*step 3：贪心构造字典序最大的最长公共子序列。lastA、lastB 表示上一个已经选中的元素在 A、B 中的位置。下一次只能选：i > lastAposB[a[i]] > lastB同时，为了保证最终长度仍然能达到最长，当前还需要 need 个元素时，只能选 dp[i] >= need 的点。在所有合法点里，直接选数值最大的 a[i]。因为字典序比较首先看当前位，所以当前位能选多大就必须选多大。*/vector<int> answer;int lastA = 0;int lastB = 0;for (int need = longest; need >= 1; need--) {// 加入所有 dp == need 的点，使结构内包含所有 dp >= need 的候选。for (int i : bucket[need]) {int x = n - i + 1;int y = n - posB[a[i]] + 1;bit2.update(x, y, a[i]);}// 查询 i > lastA 且 posB[a[i]] > lastB 的候选最大值。int maxX = n - lastA;int maxY = n - lastB;int chosenValue = bit2.query(maxX, maxY);answer.push_back(chosenValue);// 因为数组是排列，所以 chosenValue 在 A、B 中的位置唯一。lastA = posA[chosenValue];lastB = posB[chosenValue];}cout << longest << '\n';for (int i = 0; i < (int)answer.size(); i++) {if (i > 0) {cout << ' ';}cout << answer[i];}cout << '\n';return 0;
}