最小字典序的相邻交换问题：双向链表+树状数组+惰性删除堆

先说一句：这题我一开始是奔着“贪心 + 单调队列”去想的，结果被数据范围教做人。后来在赛场上改出“双向链表 + 树状数组 + 惰性删除堆”的组合才跑过去，回头复盘的时候越看越觉得这套结构值得单独写一篇。如果你正在备赛，想搞懂这类“相邻交换若干次求最小字典序”的题，这篇应该能帮你省下不少试错时间。

1. 先把题意翻译成人话：相邻交换K次的最小字典序问题

1.1 原题模型与样例

某高校校赛的 I 题《字典序》，题面很简洁：给你一个 1 到 n 的排列 a，每次操作可以挑选任意一个数，让它和相邻的数交换位置一次。问在最多 k 次操作内，能够得到的字典序最小的排列是什么。

注意三个关键字：相邻交换、最多 k 次、字典序最小。因为每交换一次只移动一格，所以一个数如果要向左跨过 x 个数，就要消耗 x 次操作。这个“代价”的感知一旦建立，后面的贪心模型就顺了。数据范围我给的是 n ≤ 2e5，k 可以大到 1e18，所以所有跟 k 有关的计算必须用 64 位整数。

我用自己的样例跑一下，方便你看懂流程：

输入 5 3 2 5 1 4 3

当前剩余序列是2 5 1 4 3，k=3，候选窗口是前 min(5, 3+1) = 4 个元素2 5 1 4，里面最小的是 1，它排在剩余序列的第 3 位。把它提到队首需要跨过 2 个元素，消耗 2 次操作，k 变成 1。此时序列变成1 2 5 4 3（注意 2 和 5 的相对顺序没变）。

接着确定第二位：剩余序列是2 5 4 3，候选窗口是前 min(4, 1+1) = 2 个元素2 5，最小的是 2，它已经在队首，消耗 0 次，直接固定。此时序列前缀是1 2。

确定第三位：剩余序列5 4 3，窗口前 2 个是5 4，最小值 4 在第 2 位，跨过 1 个元素，消耗 1 次，k 变 0。序列变成1 2 4 5 3。之后 k=0 无法再操作，直接拼接剩余元素，答案就是1 2 4 5 3。

1.2 候选窗口为什么是“前 k+1 个元素”

很多人第一眼会以为”所有元素都能作为候选“，然后直接取全局最小值，这是错的。假设当前剩余序列长度为 m，一个元素在剩余序列中的位置是 r（从 1 开始编号），把它移动到队首需要和左边的 r-1 个元素依次交换，代价是 r-1。

因此可行条件只有一个：r - 1 ≤ k，也就是 r ≤ k+1。再考虑上剩余长度 m，候选就是前min(m, k+1)个位置中的元素。

这部分的贪心直觉很直白：字典序第一位越小越好，所以在能提到队首的元素里选最小的那个固定下来；固定后问题就变成规模更小、剩余操作次数更少的子问题。这个“选窗口内最小值”的过程会重复 n 次，真正难的不是贪心，而是每次选完之后怎么继续快速维护新的窗口。

2. 简单贪心为什么会TLE：每轮“从队头往后扫”是O(N²)

2.1 朴素实现：重建序列即可，但代价太大

如果 n 只有 2000，这道题没有任何难度。每轮拿一个数组存当前剩余序列，从第 1 个位置扫到第 min(m, k+1) 个位置，找到最小值的位置，把它取出来放到答案里，然后删除这个位置，把后面的元素整体前移。伪代码长这样：

vector<int> cur = a; for (int i = 1; i <= n; i++) { int d = min((long long)cur.size(), k + 1); int pos = 0; for (int j = 1; j <= d; j++) { if (cur[j] < cur[pos]) pos = j; } ans.push_back(cur[pos]); k -= (pos - 1); cur.erase(cur.begin() + pos); }

问题一眼就能看出来：找最小值是 O(d)，删除是 O(m)，总共 n 轮，最坏 O(n²)。当 n=2e5 时，这个规模在比赛时限内是跑不完的，哪怕常数再小都白搭。

2.2 为什么不能直接用单调队列/双指针滑过去

我一开始的思路是：窗口右边界一直在向右扩展，能不能用一个单调队列维护窗口内最小值？

这个想法有个很明显的坑：k 是会减少的。每选走一个数，k 会减去它跨过的步数，窗口长度min(m, k+1)可能变小也可能变大，并不是一个持续单向扩张的滑动窗口。更麻烦的是，删除一个元素后，这个元素右边的所有元素排名都会整体减 1，哪怕它们的相对顺序没变，它们“现在在第几个位置”这个信息全部失效了。

所以你需要一个能同时做三件事的结构：

1. 支持快速删除任意位置的元素；
2. 支持查询某个元素当前在剩余序列中的排名；
3. 支持快速找到“排名 ≤ k+1 的元素中值最小的那一个”。

第 1 件事用双向链表，第 2 件事用树状数组，第 3 件事用带惰性删除的小根堆。三个结构各干一件擅长的活，组合起来就是正解。

3. 核心数据结构：双向链表 + 树状数组 + 惰性删除堆

3.1 双向链表：让任意节点的摘除变成 O(1)

由于剩余序列始终是原序列删除若干元素后剩下的部分，它们的相对顺序不会被打乱。这意味着我们不需要显式地把序列复制来复制去，只需要在原下标上维护每个节点的前驱和后继。

int pre[N], nxt[N];

初始时pre[i] = i-1, nxt[i] = i+1，注意 1 和 n 的边界。删除某个下标 p 时，只需要写：

int l = pre[p], r = nxt[p]; if (l) nxt[l] = r; if (r) pre[r] = l;

关键点是：这种删除是双向的，左边节点要知道自己右边换成了谁，右边节点也要知道左边换成了谁。如果只维护单向的 next，删除一个节点后，你就不知道左边是谁了。这就是标题里“双向指向”的由来——pre 和 nxt 两个方向的指针都要实时维护。

另外，用一个head变量记录当前剩余序列的第一个元素。如果删除的元素恰好是 head，就要把 head 更新成它的后继。

3.2 树状数组维护动态排名

双向链表解决了“删谁”的问题，但还没解决“这个元素现在排第几”的问题。每个元素在剩余序列中的排名，等于当前剩余序列中，原始下标小于等于它的元素有多少个。

这恰好是树状数组的前缀和功能：定义一个 alive 数组，某个下标如果还在剩余序列中，该位置就是 1，否则是 0。那么rank(p) = BIT.query(p)。

删除下标 p 时，执行BIT.add(p, -1)，p 右边的所有元素前缀和都会自动减 1，它们的排名就同步更新了。这个设计非常优雅：链表管邻居关系，树状数组管全局排名，两者互不干扰。

3.3 惰性删除堆：窗口收缩时怎么处理过期元素

小根堆里存(a[i], i)，按值从小到大排序。每次从堆顶拿一个元素，它未必在当前窗口内，原因有两个：

• 它可能已经被删除；
• 它的当前排名可能大于min(m, k+1)，也就是够不着队首。

处理办法就是惰性删除：不真正从堆里删，而是取出来检查一下，不合法就直接丢掉，继续看下一个。每个元素最多被丢掉一次，所以堆的总体复杂度是 O(n log n)，不会退化。

这里有一个容易误解的点：堆里剩的元素越来越多“过期”，堆会不会越变越慢？不会。每个元素只会在“第一次被取出来且不合法”时被丢弃一次，之后永远不会再进堆。所以堆操作总数是 O(n) 次 push 加上 O(n) 次 pop。

为什么不能用普通优先队列直接取最小值，非要配合 BIT 判断？因为全局最小值可能排在很后面。例如 k=2，候选窗口只有前 3 个元素，全局最小值却在原序列的第 100 位，它需要 99 次交换才能提到队首，当前操作次数根本不够。这时候堆顶要抛弃，继续找次小值，直到找到一个排在窗口内的元素。

4. 完整算法流程与核心代码

4.1 主流程逐步拆解

我把完整流程整理成下面几步，写代码的时候按这个顺序不容易乱：

1. 初始化双向链表，树状数组每个位置设为 1，把所有(a[i], i)加入小根堆。
2. 令head为原始第 1 个元素的下标，m = n。
3. 循环 m 次，每次确定答案的一位：
   • 计算当前窗口长度limit = min(m, k+1)，注意用 long long。
   • 从堆里弹出元素，直到满足条件：alive[p]为真，且BIT.query(p) <= limit。
   • 把a[p]加入答案。
   • 计算实际代价cost = BIT.query(p) - 1，执行k -= cost。
   • 从双向链表中删除 p，如果 p 是 head，则head = nxt[p]。
   • 树状数组更新BIT.add(p, -1)，m--。
4. 循环结束后，答案数组就是最小字典序排列。

这里每个元素只被选走一次，每次选走最多触发若干次堆弹出。因为每个元素最多被丢弃一次，所以整体仍然是 O(n log n)。

4.2 C++ 实现

#include <bits/stdc++.h> using namespace std; using ll = long long; const int N = 200005; int n; ll k; int a[N], pre[N], nxt[N]; bool alive[N]; struct BIT { int n; int c[N]; void init(int _n) { n = _n; for (int i = 1; i <= n; i++) c[i] = 0; } void add(int p, int v) { for (; p <= n; p += p & -p) c[p] += v; } int query(int p) { int res = 0; for (; p > 0; p -= p & -p) res += c[p]; return res; } } bit; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin >> n >> k; for (int i = 1; i <= n; i++) { cin >> a[i]; pre[i] = i - 1; nxt[i] = i + 1; alive[i] = true; } pre[1] = nxt[n] = 0; bit.init(n); for (int i = 1; i <= n; i++) bit.add(i, 1); priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq; for (int i = 1; i <= n; i++) { pq.push({a[i], i}); } int head = 1; int m = n; vector<int> ans; while (m > 0) { ll limit = min((ll)m, k + 1); int p = -1; while (!pq.empty()) { auto [val, id] = pq.top(); pq.pop(); if (!alive[id]) continue; if ((ll)bit.query(id) > limit) continue; p = id; break; } ans.push_back(a[p]); int cost = bit.query(p) - 1; k -= cost; alive[p] = false; bit.add(p, -1); int l = pre[p], r = nxt[p]; if (l) nxt[l] = r; if (r) pre[r] = l; if (head == p) head = r; m--; } for (int i = 0; i < n; i++) { cout << ans[i] << (i + 1 == n ? '\n' : ' '); } return 0; }

这段代码有几个细节值得说：pre[1] = nxt[n] = 0是为了避免删除 1 或 n 时访问到越界下标；limit必须转成 long long，因为 k 可以很大；堆里弹出时用alive判断而不是直接bit.query(id)==0判断，语义更清晰。

4.3 为什么复杂度是 O(N log N)

你可能担心“每次从堆里弹出的不合法元素会不会很多”。我们分析一下：一个元素被弹出只有两种结局——被选中固定到答案里，或者因为不在窗口内被丢弃。被选中的元素每个最多一次；被丢弃的元素同样每个最多一次。所以堆的总操作次数不超过 2n 次 push/pop。

树状数组只有删除时做 O(log n) 的单点更新，查询排名也是 O(log n)。双向链表删除是 O(1)。因此整体复杂度 O(n log n)，空间 O(n)。

5. 边界情况与对拍验证：这几处坑我调了一下午

5.1 K 特别大或者特别小

当 k ≥ n 时，窗口长度始终等于剩余序列长度，等价于每次可以从所有元素中挑最小值。对于排列，最终结果一定是1, 2, ..., n。这种时候可以用特判直接输出排序结果，省去堆和链表操作。

当 k = 0 时，limit 始终等于 1，窗口里只有队首元素。此时每次弹出的堆顶可能都是不合法元素，会不断丢弃，直到最后弹出 head 指向的那个元素。虽然正确，但多了一些无效弹出。如果你在意常数，可以在 k=0 时直接输出剩余序列。

实际比赛里 k 很少给到 0，但 k 从大变小后，堆里的“过期元素”会集中出现一波。不要因为这个现象怀疑算法正确性，这是惰性删除的正常表现。

5.2 如果序列不是排列，存在相同值怎么办

原题是排列，但很多同类题会放宽成可重复序列。存在相同值时，堆的排序要用(a[i], i)，这样值相同的情况下会优先取原始下标更小的元素。道理很简单：两个相同值的元素对字典序的贡献一样，但下标更小意味着它离队首更近，消耗的操作次数更少，留下更多操作次数给后续位置，一定不劣。这个改动非常小，写成pair<int,int>放进堆即可。

5.3 对拍程序与暴力验证方法

写这种贪心数据结构题，我个人的习惯是先写一个暴力程序对拍，不要直接对着正解调。比如 n ≤ 6，k ≤ 8 的时候，可以直接枚举所有相邻交换的状态，用 BFS 求出最小字典序终态：

map<vector<int>, int> dist; queue<vector<int>> q; dist[a] = 0; q.push(a); while (!q.empty()) { auto cur = q.front(); q.pop(); int d = dist[cur]; if (d == k) continue; for (int i = 0; i + 1 < cur.size(); i++) { swap(cur[i], cur[i + 1]); if (dist.find(cur) == dist.end()) { dist[cur] = d + 1; q.push(cur); } swap(cur[i], cur[i + 1]); } } // 在所有可达状态中取字典序最小

然后随机生成 n ≤ 6 的排列和随机的 k，把 BFS 结果和正解结果对比。我实测跑了 200 组左右，除了最初几版代码因为双向链表删 head 没更新导致错误之外，其余全部一致。

5.4 实测中的三个经典Bug

第一个 Bug：删除 p 后，没有判断 p 是不是 head，导致 head 一直指向一个已经被删掉的节点。这个在删除靠前元素时必现，排查起来也很简单——每次删除后用alive[head]校验一下就知道。

第二个 Bug：树状数组的活标记和双向链表的删除不同步。我在删除时先删链表、后加树状数组，中间有一次查询 rank 用了旧数据，导致 cost 算错。正确顺序是：先固定答案、再算 cost、再删除链表和树状数组。顺序千万不要倒过来。

第三个 Bug：k 用 int 存，结果 k 减去 cost 后溢出变成负数，导致 limit 计算出错。这个问题在本地小数据测不出来，因为小数据 k 很小；一旦换成接近 1e18 的数据就当场崩。用 long long 之后才稳。

这几类问题其实都很隐蔽，光靠肉眼不容易发现，所以建议你写题的时候顺手把 assert 加上，比如每次删除前检查alive[p]，每次更新 head 后检查alive[head]。等对拍稳定了再删掉也不迟。

如果让我重打这题，我会先花十分钟把 BFS 暴力和对拍脚本写好，再去想正解。因为这类贪心题目真正的风险不在“贪心对不对”，而在“数据结构维护得对不对”，而对拍是验证这套维护逻辑最快的方式，没有之一。