1. 从最长公共子序列到最长递增子序列的转化思路
第一次看到"UPC——Swap"这个标题，很多人会以为是一道关于交换操作的模拟题，但真正做过这类题的人都知道，它的内核其实是**最长公共子序列（LCS）转最长递增子序列（LIS）**的经典优化套路。这个转化思路在算法竞赛里出现频率极高，尤其是当两个序列都是排列（每个元素只出现一次）的时候，原本 O(n²) 的 LCS 动态规划会直接超时，必须换一条路走。
先说清楚这个转化到底解决什么问题。标准的 LCS 问题是：给两个序列 A 和 B，求它们最长的公共子序列长度。经典做法是二维 DP，dp[i][j]表示 A 的前 i 个和 B 的前 j 个的 LCS 长度，转移方程是：
- 若
A[i] == B[j]，则dp[i][j] = dp[i-1][j-1] + 1 - 否则
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
这个做法时间复杂度 O(n²)，空间也是 O(n²)。当 n 达到 1e5 甚至更大时，直接爆掉。但如果题目保证两个序列都是1 到 n 的排列（也就是每个数恰好出现一次），我们就可以把问题转化成 LIS，用 O(n log n) 解决。
转化的核心逻辑是这样的：把 A 中的每个元素映射成它在 A 中的下标位置，然后遍历 B，把 B 中每个元素替换成它在 A 中的位置，得到一个位置序列 P。此时，A 和 B 的公共子序列长度，就等于 P 的最长递增子序列长度。原因很直观：公共子序列要求在 A 和 B 中出现的顺序一致，而 P 中递增的位置序列，恰好对应着在 A 中顺序递增、在 B 中也顺序递增的一组元素。
举个具体例子。A = [3, 1, 4, 2]，B = [1, 4, 2, 3]。先建立 A 的位置映射：3→1，1→2，4→3，2→4。然后遍历 B，把每个元素换成位置：1→2，4→3，2→4，3→1，得到 P = [2, 3, 4, 1]。P 的最长递增子序列是 [2, 3, 4]，长度为 3，所以 LCS 长度就是 3。验证一下，A 和 B 的公共子序列 [1, 4, 2] 长度确实是 3。
这个转化的精妙之处在于，它把一个二维的匹配问题压成了一维的单调性问题。LIS 有经典的贪心 + 二分做法，维护一个"最小结尾数组"tails，遍历 P 时用二分找到第一个大于等于当前值的位置替换，最终tails的长度就是 LIS 长度。整个过程 O(n log n)，空间 O(n)，对于 n = 1e5 的数据完全够用。
但这里有个前提必须强调：只有当两个序列都是排列（元素互不重复）时，这个转化才严格成立。如果序列中有重复元素，映射关系就不再是一对一的，直接套用会出错。遇到有重复元素的情况，需要把同一个值在 A 中的所有位置按降序排列后依次加入 P，这样才能保证同一个值不会被重复计入递增子序列。这个细节后面会专门展开讲。
理解了转化原理，再看"Swap"这个词就顺理成章了。很多题目会在这个基础上加一层包装，比如"允许交换 B 中相邻两个元素若干次，问最多能匹配多长"，或者"通过交换操作让两个序列的 LCS 最大"。本质上还是先转成 LIS，再在 LIS 的框架上做文章。所以标题里的"Swap"不是干扰项，而是提示你这道题的最终落点仍然在 LIS 上。
2. 位置映射表的构建细节与常见错误
转化思路说起来简单，但真正动手写的时候，位置映射表的构建是最容易翻车的地方。我见过太多人思路完全正确，结果因为映射表建错导致答案偏小或者偏大，调试半天找不到问题。这一节把映射表的构建拆开讲透。
2.1 映射方向的选择：为什么是 A 映射到 B 而不是反过来
映射方向的选择看似对称，实际上有讲究。标准做法是：以 A 为基准建立"值→位置"的映射，然后遍历 B 生成位置序列。为什么不是反过来？因为 LIS 要求的是递增，而递增对应的是"A 中的顺序"。我们以 A 为基准，P 中每个值代表该元素在 A 中的位置，P 递增就意味着这些元素在 A 中出现的顺序是递增的，同时它们在 B 中也是按遍历顺序出现的，自然满足公共子序列的顺序要求。
如果反过来以 B 为基准，遍历 A 生成位置序列，得到的 LIS 长度其实是一样的，因为 LCS 是对称的。但在实际编码中，以哪个为基准会影响映射表的构建方式和后续处理。我个人的习惯是以长度较短的那个序列为基准建映射，这样映射表更小，遍历另一个序列时二分查找的缓存局部性也更好。当然，如果两个序列等长，随便选一个都行。
2.2 重复元素的处理：降序插入是关键
前面提到，如果序列中有重复元素，直接映射会出错。具体错在哪里？假设 A = [1, 1, 2]，B = [1, 2, 1]。以 A 建映射，1 对应位置 1 和 2，2 对应位置 3。如果简单地把 1 映射成某一个位置（比如第一个出现的 1 对应位置 1），遍历 B 得到 P = [1, 3, 1]，LIS 长度是 2。但实际 LCS 长度是多少？A 和 B 的公共子序列 [1, 2] 或 [1, 1] 长度都是 2，所以答案确实是 2，这个例子碰巧对了。
换一个例子：A = [1, 1, 2]，B = [1, 1, 2]。如果 1 只映射到位置 1，P = [1, 1, 3]，LIS 是 [1, 3] 长度 2，但实际 LCS 是 [1, 1, 2] 长度 3。这就错了。问题在于，B 中的两个 1 应该分别对应 A 中两个不同的 1，才能同时计入。
正确的做法是：对于 A 中同一个值的所有出现位置，按降序排列后依次加入 P。为什么是降序？因为同一个值在 B 中连续出现时，我们希望它们在 P 中对应的位置是递减的，这样 LIS 不会把它们同时选中（因为递增序列不能选递减的位置），从而避免同一个值被重复匹配到 A 中的同一个位置。等等，这个说法需要再仔细想一下。
实际上，降序插入的目的是：当 B 中同一个值出现多次时，我们希望这些出现能匹配到 A 中不同的位置，且匹配的位置在 A 中也是递增的。假设 A 中值 v 出现在位置 p1 < p2 < p3，B 中值 v 出现了两次。如果按升序插入，P 中会出现 p1, p2, p3 这样的递增片段，LIS 可能同时选中 p1 和 p2，对应 B 中两个 v 匹配 A 中位置 p1 和 p2 的两个 v，这是合法的。但如果按降序插入，P 中出现 p3, p2, p1，LIS 只能选其中一个，反而少算了。
这里我之前的理解有偏差，需要纠正。正确的处理方式是：对于 B 中每个元素，把它替换成它在 A 中所有出现位置的降序序列。注意是"B 中每个元素"展开成多个位置，而不是"A 中每个值"展开。这样做的原因是：B 中一个元素只能匹配 A 中一个位置，但我们在生成 P 时不知道应该匹配哪个，所以把所有可能的位置都列出来，用降序保证同一个 B 元素不会同时匹配多个 A 位置（因为降序序列本身不递增，LIS 最多选一个）。
举个例子：A = [1, 1, 2]，B = [1, 1, 2]。A 中 1 的位置是 [1, 2]，2 的位置是 [3]。遍历 B：第一个 1 展开成 [2, 1]，第二个 1 展开成 [2, 1]，2 展开成 [3]。P = [2, 1, 2, 1, 3]。LIS 长度是 3（选 1, 2, 3 或者 2, 3 等），实际 LCS 是 3，正确。
再验证一个：A = [1, 1, 2]，B = [1, 2, 1]。P = [2, 1, 3, 2, 1]。LIS 长度是 2（比如 1, 3 或 2, 3），实际 LCS 是 2，正确。
所以关键点是：展开的是 B 中的元素，展开成它在 A 中所有出现位置的降序序列。这个细节在纯排列的情况下不需要考虑（因为每个值只出现一次，展开就是一个数），但一旦有重复就必须处理，否则答案会错。
2.3 映射表的数据结构选择
对于纯排列的情况，映射表就是一个数组pos，pos[value] = index，O(1) 查询。对于有重复元素的情况，需要一个value -> list of positions的映射，可以用哈希表或者数组套 vector。如果值域不大（比如 1 到 n），直接用vector<vector<int>>或者vector<int> posList[n+1]更高效，避免哈希表的常数开销。
构建映射表的代码大概长这样：
// 纯排列情况 vector<int> pos(n + 1); for (int i = 0; i < n; i++) { pos[A[i]] = i; } vector<int> P; for (int i = 0; i < m; i++) { P.push_back(pos[B[i]]); }// 有重复元素情况 vector<vector<int>> pos(n + 1); for (int i = 0; i < n; i++) { pos[A[i]].push_back(i); } // 每个位置列表已经是升序，需要降序 for (int v = 1; v <= n; v++) { reverse(pos[v].begin(), pos[v].end()); } vector<int> P; for (int i = 0; i < m; i++) { for (int p : pos[B[i]]) { P.push_back(p); } }注意，如果 B 中有元素在 A 中不存在，pos[B[i]]为空，直接跳过即可，不影响结果。
3. LIS 的二分贪心实现与边界处理
生成了位置序列 P 之后，剩下的就是求 P 的 LIS。LIS 的 O(n log n) 做法是经典的贪心 + 二分，但里面的边界条件如果不注意，很容易写出 bug。这一节把 LIS 的实现细节和常见坑点讲清楚。
3.1 tails 数组的语义与更新规则
LIS 的贪心做法维护一个数组tails，其中tails[k]表示长度为 k+1 的递增子序列的最小结尾元素。这个定义是理解整个算法的关键。为什么维护"最小结尾"？因为结尾越小，后面越容易接上更大的元素，子序列越容易变长。
遍历 P 中每个元素 x 时，在tails中二分查找第一个大于等于x 的位置：
- 如果找到，用 x 替换该位置的值（因为 x 更小，作为同样长度的结尾更优）
- 如果没找到（x 比所有 tails 都大），把 x 追加到 tails 末尾（LIS 长度加一）
最终tails的长度就是 LIS 长度。注意tails本身不一定是某个具体的 LIS，它只是记录了每个长度的最优结尾。
用 C++ 的lower_bound实现：
vector<int> tails; for (int x : P) { auto it = lower_bound(tails.begin(), tails.end(), x); if (it == tails.end()) { tails.push_back(x); } else { *it = x; } } int lis = tails.size();这段代码看起来简单，但有几个地方容易出错。
3.2 严格递增还是非严格递增：lower_bound 与 upper_bound 的选择
lower_bound找的是第一个大于等于x 的位置，upper_bound找的是第一个大于x 的位置。用哪个取决于题目要求的是严格递增还是非严格递增。
对于 LCS 转 LIS 的标准场景，要求的是严格递增，因为公共子序列中同一个位置不能被重复使用，而且我们通过降序展开已经保证了同一个 B 元素不会匹配多个 A 位置。所以用lower_bound。
但如果题目允许重复匹配（比如求最长非递减公共子序列），就需要用upper_bound。这个区别在纯排列的情况下不明显（因为位置不会重复），但在有重复元素的情况下很关键。我踩过一次坑：有道题求的是"最长公共子序列允许相同元素匹配多次"，我用了lower_bound，结果答案偏小，改成upper_bound才对。
3.3 空序列与单元素序列的边界
如果 P 为空（比如 A 和 B 没有公共元素），tails为空，LIS 长度为 0，这是正确的。如果 P 只有一个元素，tails长度为 1，也正确。这些边界情况在代码里不需要特殊处理，lower_bound和push_back的逻辑自然覆盖。
但有一个隐蔽的边界：如果 P 中有元素为 0（比如位置从 0 开始编号），而tails初始为空，lower_bound返回begin()，替换第一个元素，没问题。但如果位置从 1 开始编号，也不影响。真正需要注意的是位置的值域，确保二分查找的比较不会溢出或者类型不匹配。
3.4 时间复杂度与常数优化
LIS 的 O(n log n) 已经很快了，但在极端数据下（n = 1e6），常数还是值得优化。几个技巧：
- 用数组代替 vector，避免动态扩容
- 手写二分代替
lower_bound，减少函数调用开销 - 如果 P 的值域不大，可以用树状数组求 LIS，O(n log n) 但常数更小
不过对于大多数题目，标准库的lower_bound已经足够。我实测下来，n = 1e5 的数据，标准写法跑 10ms 以内，完全够用。
4. Swap 操作在 LCS-LIS 框架下的处理方式
标题里的"Swap"是这道题区别于普通 LCS 转 LIS 的关键。很多题目会在转化之后加一层交换操作，比如"允许交换 B 中相邻两个元素 k 次，问最大 LCS"，或者"通过交换操作使两个序列的 LCS 最大"。这一节讨论几种常见的 Swap 变体以及处理思路。
4.1 相邻交换与逆序数的关系
如果题目允许交换 B 中相邻两个元素任意次，那么 B 可以变成任意排列。此时问题退化成"求 A 和 B 的最长公共子序列，其中 B 可以任意重排"，答案就是 A 和 B 的公共元素集合大小（因为 B 可以重排成和 A 的公共部分顺序一致）。这太简单了，通常题目会限制交换次数。
如果限制交换次数为 k，那么问题变成：在 B 的所有"与 B 的逆序数差不超过 k"的排列中，找与 A 的 LCS 最大的那个。这个问题就复杂了，通常需要 DP 或者其他技巧，不在本文讨论范围内。
更常见的是另一种包装：允许交换 A 中相邻两个元素，问最少交换多少次能使 A 和 B 的 LCS 达到某个值。这个问题的核心还是 LCS 转 LIS，但需要在 LIS 的基础上计算逆序数。
4.2 交换操作转化为 LIS 上的选择问题
有一类题目是这样的：给两个排列 A 和 B，允许交换 B 中任意两个元素（不限制相邻），问最少交换多少次能使 LCS 长度达到 n（即 A 和 B 完全相同）。这个问题的答案是：把 B 通过位置映射转成 P，然后求 P 的逆序数，因为每次交换可以消除一个逆序，最少交换次数就是逆序数。
如果目标不是完全相同，而是 LCS 达到某个值 L，那么问题变成：在 P 中找一个长度为 L 的递增子序列，使得把这个子序列之外的元素通过交换调整到正确位置所需的交换次数最少。这个问题的解法通常涉及 LIS 的变体，需要同时维护长度和交换代价。
4.3 一个具体的 Swap 变体实战
假设题目是：给两个排列 A 和 B，允许交换 B 中相邻两个元素，问最少交换多少次能使 A 和 B 的 LCS 长度至少为 k。这个问题的思路是：
- 把 B 转成位置序列 P
- 在 P 中找一个长度为 k 的递增子序列，使得这个子序列的"相邻元素在原 B 中的距离之和"最小（因为交换相邻元素把元素移到目标位置的代价等于距离）
- 这个最小代价就是答案
第 2 步可以用 DP 做，dp[i][j]表示以 P[i] 结尾、长度为 j 的递增子序列的最小代价。转移时枚举前一个元素，时间复杂度 O(n²k)，对于小数据可以接受。大数据需要优化，比如用线段树维护前缀最小值。
这个变体的代码框架大概是这样：
// dp[i][j]: 以 P[i] 结尾，长度 j 的最小交换代价 vector<vector<int>> dp(n, vector<int>(k + 1, INF)); for (int i = 0; i < n; i++) { dp[i][1] = 0; // 长度为 1 不需要交换 for (int j = 2; j <= k; j++) { for (int p = 0; p < i; p++) { if (P[p] < P[i]) { // 代价计算：把 P[i] 移到 P[p] 后面的距离 dp[i][j] = min(dp[i][j], dp[p][j-1] + cost(p, i)); } } } }这里的cost(p, i)需要根据具体题目定义，可能是i - p - 1（相邻交换次数），也可能是其他度量。
5. 实战中的性能陷阱与调试技巧
理论讲完了，这一节分享一些实战中踩过的坑和调试技巧。这些内容在教科书里通常不会写，但实际做题时非常有用。
5.1 映射表越界与负数下标
最常见的问题是映射表越界。如果 A 中的元素值域不是 1 到 n，而是任意整数，直接用pos[A[i]]会越界。解决办法是先对 A 和 B 做离散化，把值映射到 1 到 n 的范围内。离散化的代码：
vector<int> all; for (int x : A) all.push_back(x); for (int x : B) all.push_back(x); sort(all.begin(), all.end()); all.erase(unique(all.begin(), all.end()), all.end()); for (int &x : A) x = lower_bound(all.begin(), all.end(), x) - all.begin() + 1; for (int &x : B) x = lower_bound(all.begin(), all.end(), x) - all.begin() + 1;离散化之后，值域就是 1 到 all.size()，映射表大小按这个开。
另一个坑是负数下标。如果位置从 0 开始编号，而tails初始为空，lower_bound返回begin()，替换第一个元素，没问题。但如果代码里用了tails[x]这种直接索引，x 为 0 时会访问第一个元素，逻辑上可能不对。建议统一用迭代器或者lower_bound的返回值。
5.2 二分查找的比较函数写反
lower_bound默认用<比较，找第一个不小于目标值的位置。如果手写二分，很容易把比较方向写反。我见过有人写成找第一个不大于的位置，结果 LIS 求出来是递减的。手写二分的正确写法：
int l = 0, r = tails.size(); while (l < r) { int mid = (l + r) / 2; if (tails[mid] < x) { l = mid + 1; } else { r = mid; } } // l 就是第一个 >= x 的位置注意tails[mid] < x对应的是找第一个>= x的位置。如果写成tails[mid] <= x，就变成找第一个> x的位置，对应非严格递增。
5.3 大数据下的内存与缓存优化
当 n 达到 1e6 时，P 数组和 tails 数组各占 4MB（int），总共 8MB，通常没问题。但如果用 vector 且频繁 push_back，可能会有多次扩容和拷贝。建议提前reserve或者直接用静态数组。
另一个优化是：如果 P 的值域不大，可以用vector<int>代替set或map，减少常数。我实测过，n = 1e6 时，数组版比 set 版快 5 倍以上。
5.4 调试技巧：小数据对拍
LCS 转 LIS 的代码一旦写错，很难通过看代码发现。最有效的调试方法是小数据对拍：写一个 O(n²) 的暴力 LCS，随机生成小规模数据（n <= 10），比较两个程序的输出。如果结果不一致，打印出具体的 A、B、P 和 tails 数组，逐步排查。
对拍的代码框架：
while (true) { int n = rand() % 10 + 1; vector<int> A = random_permutation(n); vector<int> B = random_permutation(n); int ans1 = solve_fast(A, B); int ans2 = solve_brute(A, B); if (ans1 != ans2) { print(A, B, ans1, ans2); break; } }这个技巧帮我抓出过好几次 bug，尤其是重复元素处理和二分边界的问题。
6. 从 LCS-LIS 延伸出的几个变体问题
掌握了 LCS 转 LIS 的基本套路之后，可以尝试解决一些变体问题。这些变体在竞赛中经常出现，思路都是在基本框架上做调整。
6.1 最长公共上升子序列（LCIS）
LCIS 要求公共子序列既是 A 的子序列，又是 B 的子序列，同时还是严格递增的。这个问题的经典做法是 O(n²) 的 DP，但也可以用 LCS 转 LIS 的思路优化。具体做法是：以 A 为基准建映射，遍历 B 生成 P，然后在 P 中求 LIS，但要求 LIS 对应的元素值也是递增的。这个约束使得问题变复杂，通常需要结合值域信息做 DP。
6.2 多个序列的 LCS
如果有三个或更多序列，求最长公共子序列，LCS 转 LIS 的方法就不适用了，因为位置映射不再是一维的。多维 LCS 是 NP-hard 问题，通常只能用近似算法或者限制数据规模。
6.3 带权 LCS
如果每个元素匹配有不同的权重，求最大权重的公共子序列，LCS 转 LIS 的框架仍然可用，但 LIS 部分需要改成求最大权递增子序列，可以用线段树或树状数组优化。
6.4 动态 LCS
如果序列会动态修改（插入、删除元素），求 LCS 的实时值，问题就非常复杂了。通常需要用到一些高级数据结构，不在本文讨论范围内。
7. 个人实操体会与几个容易忽略的细节
最后分享几个我在实际做题中总结的细节，这些内容在题解里通常不会写，但确实能帮你少走弯路。
第一个细节是映射方向的选择会影响代码的简洁度。以较短的序列为基准建映射，遍历较长的序列生成 P，这样 P 的长度是较长的那个，但映射表更小。如果两个序列长度差异很大，这个选择能省不少内存。
第二个细节是重复元素的降序展开只在必要时做。如果题目保证是排列，直接映射即可，不需要展开。展开会增加 P 的长度，可能影响性能。我见过有人无脑展开，结果 P 的长度变成 O(n²)，直接超时。
第三个细节是LIS 的 tails 数组不一定是最终答案的子序列。很多人调试时打印 tails，发现它和预期的 LIS 不一样，就以为代码错了。其实 tails 只是记录了每个长度的最小结尾，最终答案的长度是对的，但具体子序列需要额外记录前驱才能还原。
第四个细节是注意题目要求的是长度还是具体子序列。如果只求长度，LIS 的贪心做法就够了。如果要求具体子序列，需要在更新 tails 时记录每个元素的前驱，最后回溯。回溯的代码稍微复杂一点，但思路清晰。
第五个细节是多组测试数据的清空问题。如果题目有多组测试，每组的映射表和 tails 都要清空，否则会串数据。我踩过一次坑，第二组数据的答案总是偏大，查了半天发现是第一组的 tails 没清空。
这些细节看起来琐碎，但实际做题时每一个都可能让你卡住。把基本框架写熟之后，多注意这些边界情况，基本就能稳定 AC 了。
