优化技巧)
★ FEATURED ARTICLE 第一次在比赛里看到这道I题题面读起来不长核心就三个字字典序。但我很清楚凡是这种“删几个数、拼个序列、求字典序最大/最小”的题十个里有九个不是真的让你排序而是考你手里有没有一套能在动态变化的序列里快速决策的数据结构。这道题标题里的“双向指向”和“优化技巧”其实已经暗示了解法的大方向你需要维护剩余元素之间的前后关系并且把每次删除造成的影响压缩到极小范围。这篇文章就按我自己的复盘思路来写先把题面还原成最常见的版本再一步步拆贪心规则、双向链表的作用、set配合维护候选点的方式最后把现场容易踩的坑和几个值得记住的变体一并讲掉。1. 题目到底在问什么一个典型的“删数使字典序最优”模型1.1 按同类经典题复原的题面原始题面的包装可能有出入但核心模型在竞赛里很常见给定一个长度为n的数组a希望连续删除k个数每次都必须删掉一个“当前最优”的位置使得删除后剩余序列的字典序最大或者最小并要求输出每次删除的是原数组中的哪个下标。举个例子假设a [7, 9, 8]目标是让剩余序列字典序最大。如果删位置1得到[9, 8]如果删位置2得到[7, 8]。两者从第一位开始比9 7显然删位置1更好。问题就是这个“更好”只是在一次删除里成立如果接下来还要继续删每次都要重新找。这类题最迷惑人的点在于你在纸上手算时一眼能看出答案但当n和k都是2e5规模时每次删一个数还要重新比较整个序列的字典序时间复杂度会立刻失控。1.2 先说清楚字典序比较的两条铁律字典序比较看起来只是“从头往尾比第一个不同元素”实际操作时很多人会忽略两个问题。第一比较的是“剩余序列”而不是原数组。删除位置不同剩余序列长度虽然相同但元素来源和顺序都会有差异所以不能简单拿原数组的某些区间直接比。第二一旦出现相同前缀必须一直往后跳直到找到第一个不同的位置为止。这个“跳过相同前缀”的操作在朴素写法里就是一次O(n)扫描。而后续所有优化本质上都是在想办法让这个扫描变快或者让需要比较的候选数量变少。1.3 朴素做法为什么必然超时最容易想到的做法是每一轮枚举所有剩余位置模拟删除某个位置后生成新序列再和当前最优方案做一次字典序比较。枚举位置是O(n)比较序列又是O(n)总复杂度直接变成O(n^2)。在n 2e5的规模下4e10次操作意味着即使本机跑得再快比赛时限内也不可能跑完。更麻烦的是直接用vector模拟删除每删一次数组整体左移也是O(n)这和枚举位置叠加在一起会让复杂度更难看。所以这道题的关键就变成了两件事用什么数据结构维护“删除后的剩余序列”以及用什么方式快速判断“哪个位置是当前最优删除点”。这两个问题正好对应标题里的“双向指向”和“优化技巧”。2. 核心思路为什么“双向指向”是天然的选择2.1 想让字典序变大应该删除哪种位置先说结论如果要让剩余序列的字典序最大每一步应该删除当前序列中从左到右第一个上升沿的左端点。所谓上升沿就是满足a[i] a[i1]的位置i。为什么是这个位置因为在删除i之后原来位于i1的元素会整体左移一位新序列的第i位变成了原来更大的那个元素。字典序比较从第一位开始看第一位变大的方案一定优于其他方案如果第一位相同那就继续看第二位所以要先保证最靠左的上升沿被处理掉。比如a [5, 3, 6, 4]第一个上升沿是位置23 6删除位置2得到[5, 6, 4]而删除位置1得到[3, 6, 4]第一位5 3显然是删除位置2更优。如果序列本身已经单调递减没有任何上升沿就删除最右边的元素因为此时删掉末尾会让整体字典序最大。如果要让剩余序列字典序最小规则完全对称每次删除从左到右第一个下降沿的左端点即满足a[i] a[i1]的位置i如果没有下降沿就删末尾。2.2 双向链表承担的角色维护“活着的元素”知道了删哪里还不够还需要知道删除之后数组变成什么样。朴素数组模拟在删除后需要搬移元素而用双向链表就完全没有这个烦恼。具体做法是定义左右指针数组L[]和R[]初始状态是L[i] i - 1R[i] i 1再把数组的头尾分别接到哨兵节点0和n1上。删除某个节点x时只需要两行代码R[L[x]] R[x]; L[R[x]] L[x];这两行做完x就相当于从未存在过它左右两侧的节点已经直接连在一起。整个操作是真正的O(1)不需要搬动任何其他元素。有人可能会问用标记数组del[]模拟删除不也能做到O(1)吗确实能但标记数组最大的问题是当你需要“找某个节点的前驱或后继”时必须不断跳过已删除节点最坏情况会退化回O(n)。而双向链表因为动态维护了真实的左右邻接关系任何节点都能O(1)访问到当前序列里它左边和右边的活节点这才是“双向指向”的意义所在。2.3 一个关键观察删除只影响左右两个邻居这是整道题优化的灵魂。假设当前序列存在很多上升沿我删除了节点x。其他节点的左右邻居都没有变只有x原来的前驱L[x]和原来的后继R[x]变成了新的紧邻关系。也就是说某个位置是不是上升沿只取决于它和右边活节点的值大小关系x被删除之后有资格改变“上升沿/下降沿”状态的只有它的邻居其余节点的状态全部保持不变。这个观察的直接收益是我完全不需要在每一轮结束后重新扫描整个序列去判断所有上升沿而只需要重新检查两个邻居再更新候选集合。这样每轮处理量从O(n)降成了O(1)次判断配合一个能快速取最小的数据结构总复杂度就压下来了。3. 优化技巧用set维护候选删除点把每轮决策降到log级3.1 为什么选set而不是优先队列确定了“每轮只需要重算两个邻居”之后剩下的问题就是如何快速拿到“当前最靠左的上升沿左端点”。最自然的想法是用优先队列因为它能以O(log n)取出最小值。但优先队列的麻烦在于“更新”某个位置原本是上升沿因为邻居变化不再是了这个旧信息必须被标记失效。虽然可以配合惰性删除也就是取出来时判断状态再丢弃但多轮操作后队列里会积累大量垃圾数据调试时容易眼花。所以我更推荐直接用set。它本身有序支持O(log n)插入、删除还能直接取首元素。更关键的是当某个候选点状态变化时可以直接从set里把它删掉再重新插入不需要容忍垃圾数据堆在首位。代码写起来更直观比赛时出错的概率也更低。3.2 完整维护流程初始阶段遍历所有i只要i满足a[i] a[i 1]就把i插入set。这里注意i的取值范围是从1到n-1最后一个节点没有右邻居不可能成为上升沿的左端点。每一轮删除时从set头取出一个候选位置x先验证它是否仍然满足上升沿条件。因为代码逻辑里已经保证了set中的节点都是有效状态但加上这个验证可以防一手边界笔误。如果set为空说明当前序列已经单调递减没有上升沿此时直接删除最右边的节点。删除x同时更新双向链表指针。把x的旧前驱L[x]和旧后继R[x]重新检查一次更新它们在set中的状态。这里有个容易忽略的坑删除x时要先保存l L[x]和r R[x]再去修改指针。因为一旦执行了R[L[x]] R[x]x的前驱和后继就已经换了关系此时再回头问“x的旧前驱是谁”就会得到错误答案。3.3 参考实现C#include bits/stdc.h using namespace std; const int N 200005; int n, k; int a[N], L[N], R[N]; bool del[N]; setint up; // 存储所有上升沿左端点 bool is_up(int x) { if (x 0 || x n 1 || del[x]) return false; if (R[x] n 1) return false; // 最右边节点没有后继 return a[x] a[R[x]]; // 严格上升才算上升沿 } void erase_node(int x) { int l L[x], r R[x], tail -1; // 先保存旧邻居再改指针 L[r] l; R[l] r; del[x] true; if (x tail) tail l; // 维护真实最右节点 up.erase(x); // 删除后只需要重新检查左右两个邻居 int nb[2] {l, r}; for (int t : nb) { if (t 0 || t n 1 || del[t]) continue; up.erase(t); // 删除旧状态 if (is_up(t)) up.insert(t); // 插入新状态 } } int main() { ios::sync_with_stdio(false); cin.tie(0); cin n k; for (int i 1; i n; i) cin a[i]; // 初始化双向链表 for (int i 0; i n 1; i) { L[i] i - 1; R[i] i 1; } // 初始化候选集合 for (int i 1; i n; i) { if (a[i] a[i 1]) up.insert(i); } int tail n; vectorint ans; for (int step 0; step k; step) { int x; if (!up.empty()) { x *up.begin(); // 保险起见再验证一次 while (!up.empty() !is_up(x)) { up.erase(x); x *up.begin(); } } else { x tail; // 没有上升沿删末尾 } erase_node(x); ans.push_back(x); } for (int v : ans) cout v ; cout \n; }这段代码里我顺便把tail维护进去了。因为当序列没有上升沿时需要删除的是最右边的节点如果一直维护tail变量就能直接拿到真实最右节点不用再从链头一路跳过去。3.4 为什么每轮只重算两个邻居就够了很多人写完这段代码会心里打鼓万一删除x之后x的前驱变成了一个更靠前的上升沿但它之前不在set里怎么办其实不会。因为x的前驱l和x原来的后继r接上之后l的右邻居变了所以l的上升沿状态可能反转。除此之外任何比l更靠左的节点它们的左右邻居都没有发生任何变化上升沿状态自然也不可能改变。如果某个节点之前就在set里删除后它仍然在那里会被后续轮次正常取到如果它原本不是上升沿邻居没变现在依然不是。所以每轮删除后真正需要“重新判断”的节点集合至多就是两个这就是整个“优化技巧”能成立的数学基础。4. 复杂度结论与现场最容易踩的坑4.1 复杂度到底优化到了什么程度先看暴力做法每轮枚举所有活节点找最优位置每次判断字典序又要O(n)总复杂度O(n^2)。用双向链表set后初始化O(n log n)每轮删除取出候选O(log n)删除节点O(1)重算两个邻居并更新set是两次O(log n)总复杂度O((n k) log n)在n, k均为2e5时这个复杂度可以轻松跑进一秒。就算换成性能一般的评测机也没什么压力。方法单次找最优单次删除总复杂度朴素模拟O(n)O(n)O(n^2)双向链表线性扫描O(n)O(1)O(n^2)双向链表setO(log n)O(1)O((n k) log n)4.2 坑一严格不等号经常写错判断上升沿时用的是严格小于a[x] a[R[x]]下降沿则用严格大于。这一点非常容易在紧张状态下写反。如果数组里存在相等的相邻元素比如a [3, 3, 5]在字典序最大问题里位置1的3 3不成立所以位置1不是一个有效的上升沿左端。如果用成了set里会混入本不该作为候选的节点删除顺序就错了。这类错误对拍也很难测出来因为只有数据里恰好出现大量相等元素时才会暴露。4.3 坑二维护最右tail时被哨兵误导双向链表用下标从0到n1做哨兵这时R[n] n 1而n1是个虚拟节点不能真的参与值比较。在删末尾的流程里如果不单独维护tail改成“从链表头一直往右走到哨兵前”那每次删末尾都退化成O(n)。我在现场见过的错误写法是把R[n 1]也当成真实节点去更新结果删除末尾时把哨兵也一起删了本质上是双向链表的维护方向没想清楚。正确做法是单独维护一个tail变量每次删除x时判断“x是不是当前tail”如果是就更新为L[x]。这样删末尾就始终是O(1)。4.4 坑三对拍程序是这类题的救命稻草这种带set和链表的题本地手搓几组小数据根本看不出问题尤其是当删除顺序和答案要求不一致时肉眼很难发现。我的习惯是写一个暴力函数每次枚举所有位置把剩余元素压进vector比较字典序选最优的下标再用双向链表set方法跑同一组数据循环随机生成数据并对拍。一旦发现某组不一致立刻把原始数组和双方输出一起打出来缩小到最小反例。实际调试中至少一半的bug是靠对拍而不是靠肉眼看出来的。5. 值得记住的两个扩展方向5.1 静态版如果只需要最终剩余序列单调栈更快同一个模型还有另一种常见问法不要求输出每一步删除位置只需要输出删完k个数之后最终的剩余序列。这种时候双向链表set仍然能过但有一个更简单的O(n)做法——单调栈。从左往右维护一个单调递增栈每当发现栈顶元素大于当前元素并且当前还能继续删除时就把栈顶弹出。这样最后栈里留下的就是剩余序列。双链表的“删除第一个上升沿左端”本质上和单调栈是同一个贪心规则的两种实现链表是动态删除栈是静态构造。比赛时如果只问最终序列直接写单调栈如果要求输出删除位置那双向链表set才是更自然的思路。5.2 进阶版如果题目改成“判断两种删除方案谁更优”有的题目会绕一下不让你直接维护最优位置而是反复询问“删除位置p和位置q哪个剩余序列字典序更大”。这种问题单靠双向链表不够还需要一个快速比较两个序列的方法。常见做法是预处理哈希二分两个序列的LCP长度然后比较第一个不同位置的大小。用双模数哈希避免碰撞配合O(log n)的二分单次比较复杂度是O(log n)。这个技巧本质上是把“找第一个不同点”转化为“跳过相同前缀”和本文的贪心规则正好互补。我复盘这道题时最大的收获不是set用法而是那个“删除只影响左右两个邻居”的观察。很多看似是无敌难搞的动态序列问题一旦找到这个局部性复杂数据结构就变得没那么可怕了。如果你之后遇到类似题目先别急着堆平衡树试着在纸上画一画删除一个节点之后到底有哪些节点的状态会变答案往往就藏在那个“极小范围”里。
阅读完成 · 觉得有帮助？
