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

先说一句这题我一开始是奔着“贪心 单调队列”去想的结果被数据范围教做人。后来在赛场上改出“双向链表 树状数组 惰性删除堆”的组合才跑过去回头复盘的时候越看越觉得这套结构值得单独写一篇。如果你正在备赛想搞懂这类“相邻交换若干次求最小字典序”的题这篇应该能帮你省下不少试错时间。1. 先把题意翻译成人话相邻交换K次的最小字典序问题1.1 原题模型与样例某高校校赛的 I 题《字典序》题面很简洁给你一个 1 到 n 的排列 a每次操作可以挑选任意一个数让它和相邻的数交换位置一次。问在最多 k 次操作内能够得到的字典序最小的排列是什么。注意三个关键字相邻交换、最多 k 次、字典序最小。因为每交换一次只移动一格所以一个数如果要向左跨过 x 个数就要消耗 x 次操作。这个“代价”的感知一旦建立后面的贪心模型就顺了。数据范围我给的是 n ≤ 2e5k 可以大到 1e18所以所有跟 k 有关的计算必须用 64 位整数。我用自己的样例跑一下方便你看懂流程输入 5 3 2 5 1 4 3当前剩余序列是2 5 1 4 3k3候选窗口是前 min(5, 31) 4 个元素2 5 1 4里面最小的是 1它排在剩余序列的第 3 位。把它提到队首需要跨过 2 个元素消耗 2 次操作k 变成 1。此时序列变成1 2 5 4 3注意 2 和 5 的相对顺序没变。接着确定第二位剩余序列是2 5 4 3候选窗口是前 min(4, 11) 2 个元素2 5最小的是 2它已经在队首消耗 0 次直接固定。此时序列前缀是1 2。确定第三位剩余序列5 4 3窗口前 2 个是5 4最小值 4 在第 2 位跨过 1 个元素消耗 1 次k 变 0。序列变成1 2 4 5 3。之后 k0 无法再操作直接拼接剩余元素答案就是1 2 4 5 3。1.2 候选窗口为什么是“前 k1 个元素”很多人第一眼会以为”所有元素都能作为候选“然后直接取全局最小值这是错的。假设当前剩余序列长度为 m一个元素在剩余序列中的位置是 r从 1 开始编号把它移动到队首需要和左边的 r-1 个元素依次交换代价是 r-1。因此可行条件只有一个r - 1 ≤ k也就是 r ≤ k1。再考虑上剩余长度 m候选就是前min(m, k1)个位置中的元素。这部分的贪心直觉很直白字典序第一位越小越好所以在能提到队首的元素里选最小的那个固定下来固定后问题就变成规模更小、剩余操作次数更少的子问题。这个“选窗口内最小值”的过程会重复 n 次真正难的不是贪心而是每次选完之后怎么继续快速维护新的窗口。2. 简单贪心为什么会TLE每轮“从队头往后扫”是O(N²)2.1 朴素实现重建序列即可但代价太大如果 n 只有 2000这道题没有任何难度。每轮拿一个数组存当前剩余序列从第 1 个位置扫到第 min(m, k1) 个位置找到最小值的位置把它取出来放到答案里然后删除这个位置把后面的元素整体前移。伪代码长这样vectorint 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²)。当 n2e5 时这个规模在比赛时限内是跑不完的哪怕常数再小都白搭。2.2 为什么不能直接用单调队列/双指针滑过去我一开始的思路是窗口右边界一直在向右扩展能不能用一个单调队列维护窗口内最小值这个想法有个很明显的坑k 是会减少的。每选走一个数k 会减去它跨过的步数窗口长度min(m, k1)可能变小也可能变大并不是一个持续单向扩张的滑动窗口。更麻烦的是删除一个元素后这个元素右边的所有元素排名都会整体减 1哪怕它们的相对顺序没变它们“现在在第几个位置”这个信息全部失效了。所以你需要一个能同时做三件事的结构支持快速删除任意位置的元素支持查询某个元素当前在剩余序列中的排名支持快速找到“排名 ≤ k1 的元素中值最小的那一个”。第 1 件事用双向链表第 2 件事用树状数组第 3 件事用带惰性删除的小根堆。三个结构各干一件擅长的活组合起来就是正解。3. 核心数据结构双向链表 树状数组 惰性删除堆3.1 双向链表让任意节点的摘除变成 O(1)由于剩余序列始终是原序列删除若干元素后剩下的部分它们的相对顺序不会被打乱。这意味着我们不需要显式地把序列复制来复制去只需要在原下标上维护每个节点的前驱和后继。int pre[N], nxt[N];初始时pre[i] i-1, nxt[i] i1注意 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, k1)也就是够不着队首。处理办法就是惰性删除不真正从堆里删而是取出来检查一下不合法就直接丢掉继续看下一个。每个元素最多被丢掉一次所以堆的总体复杂度是 O(n log n)不会退化。这里有一个容易误解的点堆里剩的元素越来越多“过期”堆会不会越变越慢不会。每个元素只会在“第一次被取出来且不合法”时被丢弃一次之后永远不会再进堆。所以堆操作总数是 O(n) 次 push 加上 O(n) 次 pop。为什么不能用普通优先队列直接取最小值非要配合 BIT 判断因为全局最小值可能排在很后面。例如 k2候选窗口只有前 3 个元素全局最小值却在原序列的第 100 位它需要 99 次交换才能提到队首当前操作次数根本不够。这时候堆顶要抛弃继续找次小值直到找到一个排在窗口内的元素。4. 完整算法流程与核心代码4.1 主流程逐步拆解我把完整流程整理成下面几步写代码的时候按这个顺序不容易乱初始化双向链表树状数组每个位置设为 1把所有(a[i], i)加入小根堆。令head为原始第 1 个元素的下标m n。循环 m 次每次确定答案的一位计算当前窗口长度limit min(m, k1)注意用 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--。循环结束后答案数组就是最小字典序排列。这里每个元素只被选走一次每次选走最多触发若干次堆弹出。因为每个元素最多被丢弃一次所以整体仍然是 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_queuepairint, int, vectorpairint, int, greaterpairint, int pq; for (int i 1; i n; i) { pq.push({a[i], i}); } int head 1; int m n; vectorint 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 指向的那个元素。虽然正确但多了一些无效弹出。如果你在意常数可以在 k0 时直接输出剩余序列。实际比赛里 k 很少给到 0但 k 从大变小后堆里的“过期元素”会集中出现一波。不要因为这个现象怀疑算法正确性这是惰性删除的正常表现。5.2 如果序列不是排列存在相同值怎么办原题是排列但很多同类题会放宽成可重复序列。存在相同值时堆的排序要用(a[i], i)这样值相同的情况下会优先取原始下标更小的元素。道理很简单两个相同值的元素对字典序的贡献一样但下标更小意味着它离队首更近消耗的操作次数更少留下更多操作次数给后续位置一定不劣。这个改动非常小写成pairint,int放进堆即可。5.3 对拍程序与暴力验证方法写这种贪心数据结构题我个人的习惯是先写一个暴力程序对拍不要直接对着正解调。比如 n ≤ 6k ≤ 8 的时候可以直接枚举所有相邻交换的状态用 BFS 求出最小字典序终态mapvectorint, int dist; queuevectorint 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、再删除链表和树状数组。顺序千万不要倒过来。第三个 Bugk 用 int 存结果 k 减去 cost 后溢出变成负数导致 limit 计算出错。这个问题在本地小数据测不出来因为小数据 k 很小一旦换成接近 1e18 的数据就当场崩。用 long long 之后才稳。这几类问题其实都很隐蔽光靠肉眼不容易发现所以建议你写题的时候顺手把 assert 加上比如每次删除前检查alive[p]每次更新 head 后检查alive[head]。等对拍稳定了再删掉也不迟。如果让我重打这题我会先花十分钟把 BFS 暴力和对拍脚本写好再去想正解。因为这类贪心题目真正的风险不在“贪心对不对”而在“数据结构维护得对不对”而对拍是验证这套维护逻辑最快的方式没有之一。