🎮从堆到树：一道题的两个平行宇宙
今天的任务卷轴——3691. 最大子数组总值 II——规则赫然写着：选恰好 k 个不同的非空子数组，可以重叠，同一个子数组不能被选择超过一次。求最大极差之和。
我差点笑出声。这不就是老勇者昨天拿红笔在我羊皮纸上改出来的那道“如果加上约束”吗？连标点符号都没改！直接上昨天那套代码——隧道模型 + 贪心堆 + 稀疏表。稀疏表预处理 O(n log n)，每条隧道初始最深段入堆，候选池恒定 n 个，每次弹堆顶累加极差、同一隧道缩一格压回，k 次堆操作 O(k log n)。提交，AC，一气呵成。
我往椅背上一靠，长长地舒了一口气。今天这副本过得这么快，说白了还得感谢老勇者昨天提前给我开的小灶，跟考前泄题似的。我严重怀疑这老头是策划部的内鬼。我端起茶杯，想着今天终于不用担心被弹脑瓜崩——毕竟答案是他自己教的，他总不能弹自己吧？
茶杯刚端到嘴边，茶水表面映出一个熟悉的身影。我手一抖，滚烫的茶水差点浇在裤裆上。老勇者正站在我身后，低头看着我的屏幕，表情介于"孺子可教"和"你还差得远"之间。
“大、大师……“我结结巴巴地说道，“你怎么又来了？！这题不就是昨天你红笔改的那道吗，没加新约束，原封不动！我用的是你教的隧道模型加堆加稀疏表，一个变量都没改！”
“别紧张。“老勇者笑了笑，在我肩上轻轻拍了拍——终于不是弹脑瓜崩，“昨天教你的，今天能直接用上，说明你记住了，理解了’固定一端、贪心另一端’的精髓。我来不是为了弹你，是来问你一个问题。”
“问题？“我心里咯噔一下，毕竟老勇者的"问题"通常意味着"你又掉坑里了"或者"还有更优解”。
老勇者指了指我的代码：“隧道模型加堆，k 次堆操作 O(k log n)，k 到十万的时候千万级操作量，常数拉满。如果哪天 k 飙到 10^6、10^7，你这个堆还撑得住吗？”
我倒吸一口凉气。说实话，我压根没想过这个问题。能过就行，还要什么自行车？但老勇者这么一说，我突然意识到：这解法复杂度跟 k 线性相关，k 越大越慢。现在 k ≤ 10^5 能过，但如果 k 到了 10^6、10^7 呢？如果这是一道交互题，要求在线查询呢？
“真正的勇士，“老勇者缓缓开口，“敢于直面惨淡的复杂度，敢于正视淋漓的 TLE。如果有一种方法，复杂度跟 k 彻底解耦，能在 O(n log n) 的时间内解决，不管 k 有多大都稳如泰山——你想不想学？”
我手里的茶杯"啪"地掉在地上：“O(n log n)？跟 k 无关？这都违反信息论了吧？！”
老勇者狡黠一笑，”二分答案，上古时代用来处理 Top-K 问题的禁忌魔法。它的核心思想简单得反直觉：不直接找那 k 个子数组，而是先找到第 k 大的极差值到底是多少，然后分类统计。
“等等，你是说……我不需要知道前 k 名分别是谁，只需要知道第 k 名的分数是多少？” 我感觉自己的世界观在崩塌。
“对。”老勇者打了个响指，空中应声浮现出一排数字，“就像你不需要把全班成绩单从头排到尾，只需要知道第十名的分数——然后比它高的全录，刚好压线的挑几个凑够人数，剩下的全刷。这种思路叫二分答案判定，把选择问题降维成判定问题。在很多 Top-K 场景里，都是降维打击的利器。”
第一重封印：二分答案——先找阈值，再分类统计
老勇者在卷轴背面画出一条数轴，从 0 标到 max(nums) - min(nums)。
“想象你在玩一个猜数字游戏。我告诉你：存在一个阈值 low_d，所有极差严格大于 low_d 的子数组，数量凑不够 k 个；但如果把等于 low_d 的也加上，数量就够 k 了——甚至超过 k。这个 low_d 是什么？”
我想了想：“这不就是第 k 大的极差值吗？排名刚好卡在第 k 位的那个人！”
“没错。“老勇者点点头，手指在数轴上轻轻一划，“如果我们能快速算出’有多少个子数组的极差 ≥ X’，就能用二分查找精准定位这个 low_d。找到之后，问题就拆成三块：极差严格大于 low_d 的全选；极差刚好等于 low_d 的，挑几个补满 k 个；极差小于 low_d 的直接pass。最后用选中的子数组去求和。”
我眼睛一亮：“这不就高考录取吗！先划分数线，过线的全录，压线的按志愿顺序挑，没达线的回家种地。把 Top-K 选择问题降维成一个判定问题——‘这个分数线划得合不合理？’——然后二分答案！”
“是这个道理。“老勇者笑了笑，话锋陡然一转，“不过，现在你只是知道了解法蓝图。蓝图里最关键的那块砖还没烧——怎么高效判定？给你一个阈值 X，你怎么快速统计出极差 ≥ X 的子数组到底有多少个？”
我嘴巴闭得紧紧的，心里反复默念——绝对不能提 O(n²) 暴力枚举，求生欲告诉我，沉默是金。
他瞅了瞅我：“这就引出了第二重封印——滑动窗口加单调队列。想学的话，把你脑子里那个 O(n²) 的念头掐掉，我要往里面塞点真正高效的东西。”
第二重封印：滑动窗口 + 单调队列——像塔防游戏一样收缩防线
老勇者在纸上画了一个窗口 [left, i]，左右两端各站着一个守卫，一个盯最大值，一个盯最小值。
“想象你在玩一个塔防游戏。右端点 i 是你不断往前推的兵线，每次加入一个新元素，你要维护窗口内的最大值和最小值，确保极差始终小于 X。一旦极差飙到 ≥ X，说明战线崩了，就得把左端点 left 往右挪，收缩防线，直到极差重新掉回安全线以下。”
他写下一段代码，我凑了过去，看到两个双端队列 min_q 和 max_q，一个单调递增存最小值候选，一个单调递减存最大值候选。每次 i 右移，新元素入队，过期元素被窗口淘汰。关键在最后一句：cnt += left——对于当前右端点 i，左端点在 [0, left-1] 范围内的所有子数组，极差都 ≥ X，所以直接累加 left 就是新增的数量。一旦 cnt 攒到 k，就说明这个阈值太低，数量超标了，直接打回。
def check(low_d: int) -> bool:
low_d += 1 # 实际检查的是极差 >= low_d+1
min_q = deque() # 单调递增队列，维护最小值的下标
max_q = deque() # 单调递减队列，维护最大值的下标
cnt = left = 0
for i, x in enumerate(nums):
# 1. 右边入队：维护单调性
while min_q and x <= nums[min_q[-1]]:
min_q.pop()
min_q.append(i)
while max_q and x >= nums[max_q[-1]]:
max_q.pop()
max_q.append(i)
# 2. 左边出队：收缩窗口直到极差 < low_d+1
while nums[max_q[0]] - nums[min_q[0]] >= low_d:
left += 1
if min_q[0] < left: # 队首不在窗口中
min_q.popleft()
if max_q[0] < left: # 队首不在窗口中
max_q.popleft()
cnt += left # 对于右端点i，有left个左端点使得极差 >= low_d+1
if cnt >= k:
return False # 数量够了，阈值太低
return True # 数量不够，阈值太高
low_d = bisect_left(range(max(nums) - min(nums)), True, key=check)
我盯着那段单调队列的代码，感觉似曾相识：“等等，两个双端队列一左一右夹着窗口滑过去，最大值最小值实时追踪，这不就是 1438 题’绝对差不超过限制的最长连续子数组’的经典套路吗？那道题求的是窗口能撑到多长，这道题求的是子数组数量，就差在 cnt += left 这一行！”
“没错。“老勇者点点头，“对于当前右端点 i，左端点在 [0, left-1] 范围内的所有子数组，极差全都 ≥ low_d。所以直接累加 left，数量就出来了。判定函数的返回值也反过来用：返回 True 说明数量不够，阈值太高了，得往下降；返回 False 说明数量超了，阈值太低了，得往上抬。二分夹逼到最后，第一个让 check 返回 True 的 low_d，就是第 k 大的极差值。”
“但——“他话锋一转，眼神变得危险起来，“滑动窗口只能告诉你’有多少个’子数组过线了，至于每个过线子数组的极差具体是多少、加起来总和多大，它一概不管，就像个只数人头不登记分数的门卫。”
我感觉后背开始冒汗，“既然滑动窗口只能计数不能求和，那要求极差之和，难道要把每个子数组的最大最小值都查出来？这不又退回 O(n²) 了？”
‘‘所以才需要第三重封印。“老勇者在纸上写下三个大字——单调栈，“判定靠滑动窗口，求和靠单调栈加线段树——前者是哨兵站岗，只管数人头；后者是工程兵架桥，把每一段极差的具体数值算清楚。”
第三重封印：单调栈——给每个元素划地盘
“先解决第一步——怎么快速知道每个子数组的最小值和最大值由谁当。“老勇者叩了叩桌子，“对于每个位置 i，你怎么快速找到它左边第一个 ≤ nums[i] 的位置？”
我想了想：‘‘用一个单调递增栈，从左往右扫，栈顶就是左边第一个比当前元素小的位置？’’
‘‘对。‘‘老勇者提笔唰唰写下几行代码：
n = len(nums)
left_less_eq = [0] * n # 左边第一个 <= nums[i] 的位置
left_great_eq = [0] * n # 左边第一个 >= nums[i] 的位置
st1 = [-1] # 哨兵
st2 = [-1]
for i, x in enumerate(nums):
while len(st1) > 1 and nums[st1[-1]] > x:
st1.pop()
left_less_eq[i] = st1[-1]
st1.append(i)
while len(st2) > 1 and nums[st2[-1]] < x:
st2.pop()
left_great_eq[i] = st2[-1]
st2.append(i)
“两个单调栈，一趟扫描，分别追踪左边第一个 ≤ 和第一个 > 的位置。left_less_eq[i] 表示位置 i 左边第一个 ≤ nums[i] 的位置。这意味着在区间 (left_less_eq[i], i] 内，所有元素都严格大于 nums[i]。所以，以 i 为右端点、左端点落在这个区间内的所有子数组，最小值统统是 nums[i]。’’
我惊呼道：“那 left_greater_eq[i] 就是左边第一个 ≥ nums[i] 的位置，左端点落在 (left_greater_eq[i], i] 内的所有子数组，最大值都是 nums[i]！两个数组合起来，就把每个元素作为最小值或最大值的‘地盘’划得清清楚楚！”
“没错。相当于给每个元素发了一张地契——在它的地盘里，它就是最值。“老勇者点点头，“但光有地盘还不够。你想想，随着右端点 i 不断往右移，每个左端点 j 对应的子数组 [j, i] 的最小值和最大值是动态变化的。新元素一加入，某些左端点对应的最值就要更新。你需要一个数据结构，能把这些动态变化的最值维护起来，还能快速查询任意左端点区间内的最值之和。”
我感觉脑细胞已经开始集体抗议：“今天的强度过分了啊——动态维护所有左端点的最值？还区间查询求和？这活儿谁干得了？队列不行，栈也不行，总不能上树吧——”
老勇者咳了一声，连锅炉里的火都抖了三抖，“你说对了——就是要上树。欢迎来到地狱模式的最终章：懒标记线段树。”
第四重封印：懒标记线段树——动态维护所有左端点的极值
老勇者在纸上画出一棵倒挂的二叉树，每个节点上挂着四面小旗，分别写着 sum_min、sum_max、l_min、l_max。
“线段树的下标 j 代表’以 j 为左端点，当前 i 为右端点‘的子数组 [j, i]。每个节点管一片连续的左端点区间，维护四个值——sum_min 是这个区间内所有左端点对应的当前子数组的最小值之和，sum_max 是最大值之和。l_min 和 l_max 是懒标记，代表这个区间内所有左端点被统一刷成的’共同最小值’和’共同最大值’。”
我感觉自己的 SAN 值正在狂掉：“等等，为什么存’和’？还有那个’懒标记’是什么鬼？听起来像我的拖延症一样。”
“因为你要的不是单个子数组的极差，而是’所有极差 ≥ low_d 的子数组的极差之和’。“老勇者耐心地解释，“如果你只存单个最值，查区间 [0, l] 的极差之和时，你得把 l+1 个左端点挨个捞出来，一个个减，一个个加——O(n)，求和又炸了。但每个节点提前把管辖区的 sum_max 和 sum_min 存好，一次区间查询直接拎出两个总和，极差之和 = sum_max - sum_min，O(log n) 完事。”
我恍然大悟：“所以线段树不是在存单个值，是在存’辖区总和’！每个节点提前把自己管的那段区间的账算好了，上面要查的时候直接报总数，不用一个一个数人头！”
“正是。这就是线段树的精髓——把 O(n) 的区间求和压成 O(log n) 的分块预结算。“老勇者话锋一转，“但光有查询还不够，你还得能更新。每次 i 往右移一位，新元素 nums[i] 加入，哪些左端点对应的子数组最值会变？”
我顺着他的目光看向之前写的单调栈代码：“左端点落在 (left_less_eq[i], i] 内的，最小值统统更新为 nums[i]；左端点落在 (left_greater_eq[i], i] 内的，最大值统统更新为 nums[i]。这就是两次区间赋值——每来一个新元素，就要把两片连续区间的所有左端点的最值全刷成同一个数。”
“对。区间赋值，暴力改是 O(n)，来一个元素改一片，总复杂度直接飙回 O(n²)。这时候懒标记就登场了。“老勇者指了指节点上那两面写有 l_min 和 l_max 的小旗，“以刷最小值为例——如果当前节点完全被覆盖，直接把它的 l_min 更新成 nums[i]，对应的 sum_min 就是 l_min × 区间长度，然后拍拍屁股走人，不用往下递归到每个叶子。它的子孙们先欠着，等下次查询或更新路过的时候再把这笔账还下去。这样一次区间赋值也是 O(log n)，而不是 O(n)。”
我目瞪口呆，“所以懒标记不是偷懒，是把区间赋值的活儿打包延期执行——每次只改大区间的总账，明细先欠着，等要查明细的时候再往下分摊！这不就是我平时写代码时的 ‘TODO: 稍后优化’ 吗？”
“你这说的……虽然不太恰当，但意外地准确。“老勇者嘴角抽搐了一下，“懒标记的核心思想就是延迟传播（Lazy Propagation）。更新时只改当前节点的标记和总和，不往下递归；查询或再次更新时，如果需要访问子节点，才把标记下传（spread）。这样保证每次操作都是 O(log n)。”
他提笔写下了一颗完整的懒标记线段树，看起来就像魔法阵一样：
class Node:
# val = [sum_min, sum_max, l_min, l_max]
# todo = [todo_min, todo_max]
__slots__ = 'val', 'todo'
class LazySegmentTree:
# 懒标记初始值
_TODO_INIT = [-1, -1]
def __init__(self, n: int):
# 线段树维护一个长为 n 的数组（下标从 0 到 n-1）
self._n = n
self._tree = [Node() for _ in range(2 << (n - 1).bit_length())]
self._build(1, 0, n - 1)
# 合并两个 val
def _merge_val(self, a: List[int], b: List[int]) -> List[int]:
return [a[0] + b[0], a[1] + b[1], a[2], a[3]]
# 把懒标记作用到 node 子树（本例为区间赋值）
def _apply(self, node: int, l: int, r: int, todo) -> None:
cur = self._tree[node]
# 计算 tree[node] 区间的整体变化
todo_min, todo_max = todo
if todo_min >= 0:
cur.val[0] = todo_min * (r - l + 1) # 区间最小值之和 = 最小值 × 区间长度
cur.val[2] = todo_min # 记录共同最小值
cur.todo[0] = todo_min # 设置懒标记
if todo_max >= 0:
cur.val[1] = todo_max * (r - l + 1) # 区间最大值之和
cur.val[3] = todo_max
cur.todo[1] = todo_max
# 把当前节点的懒标记下传给左右儿子
def _spread(self, node: int, l: int, r: int) -> None:
todo = self._tree[node].todo
if todo == self._TODO_INIT: # 没有需要下传的信息
return
m = (l + r) // 2
self._apply(node * 2, l, m, todo) # 下传给左儿子
self._apply(node * 2 + 1, m + 1, r, todo) # 下传给右儿子
todo[:] = self._TODO_INIT[:] # 清空当前节点的懒标记
# 合并左右儿子的 val 到当前节点的 val
def _maintain(self, node: int) -> None:
self._tree[node].val = self._merge_val(
self._tree[node * 2].val,
self._tree[node * 2 + 1].val
)
# 初始化线段树
# 时间复杂度 O(n)
def _build(self, node: int, l: int, r: int) -> None:
self._tree[node].val = [0] * 4
self._tree[node].todo = self._TODO_INIT[:]
if l == r: # 叶子
return
m = (l + r) // 2
self._build(node * 2, l, m) # 初始化左子树
self._build(node * 2 + 1, m + 1, r) # 初始化右子树
self._maintain(node)
def _update(self, node: int, l: int, r: int, ql: int, qr: int, f: Tuple[int, int]) -> None:
if ql <= l and r <= qr: # 当前子树完全在 [ql, qr] 内
self._apply(node, l, r, f)
return
self._spread(node, l, r)
m = (l + r) // 2
if ql <= m: # 更新左子树
self._update(node * 2, l, m, ql, qr, f)
if qr > m: # 更新右子树
self._update(node * 2 + 1, m + 1, r, ql, qr, f)
self._maintain(node)
def _query(self, node: int, l: int, r: int, ql: int, qr: int) -> List[int]:
if ql <= l and r <= qr: # 当前子树完全在 [ql, qr] 内
return self._tree[node].val
self._spread(node, l, r)
m = (l + r) // 2
if qr <= m: # [ql, qr] 在左子树
return self._query(node * 2, l, m, ql, qr)
if ql > m: # [ql, qr] 在右子树
return self._query(node * 2 + 1, m + 1, r, ql, qr)
l_res = self._query(node * 2, l, m, ql, qr)
r_res = self._query(node * 2 + 1, m + 1, r, ql, qr)
return self._merge_val(l_res, r_res)
def _find_last(self, node: int, l: int, r: int, ql: int, qr: int, f: Callable[[List[int]], int]) -> int:
if l > qr or r < ql or not f(self._tree[node].val):
return -1
if l == r:
return l
self._spread(node, l, r)
m = (l + r) // 2
idx = self._find_last(node * 2 + 1, m + 1, r, ql, qr, f) # 优先查右子树
if idx < 0:
idx = self._find_last(node * 2, l, m, ql, qr, f) # 右子树没有再查左子树
return idx
# 用 f 更新 [ql, qr] 中的每个 a[i]
# 0 <= ql <= qr <= n-1
# 时间复杂度 O(log n)
def update(self, ql: int, qr: int, f: Tuple[int, int]) -> None:
self._update(1, 0, self._n - 1, ql, qr, f)
# 返回用 _merge_val 合并所有 a[i] 的计算结果，其中 i 在闭区间 [ql, qr] 中
# 0 <= ql <= qr <= n-1
# 时间复杂度 O(log n)
def query(self, ql: int, qr: int) -> List[int]:
return self._query(1, 0, self._n - 1, ql, qr)
# 返回 [ql, qr] 内最后一个满足 f 的下标
# 0 <= ql <= qr <= n-1
# 时间复杂度 O(log n)
def find_last(self, ql: int, qr: int, f: Callable[[List[int]], int]) -> int:
return self._find_last(1, 0, self._n - 1, ql, qr, f)
“注意看 _ apply 方法。“老勇者指着代码，"todo_min >= 0 表示要把这个区间的最小值设为 todo_min。那么 sum_min = todo_min × 区间长度，同时设置 l_min = todo_min 和懒标记 todo[0] = todo_min。_spread 方法负责把懒标记下传给子节点，然后清空当前节点的标记。”
我感觉脑子有点转不过来：“所以下传的时候，是把父节点的懒标记应用到子节点上，然后父节点的标记清零？这就像是老板把任务分配给下属，然后自己装作什么都没发生过？”
“差不多。“老勇者点点头，“但要注意，下传之前要检查懒标记是否是初始值（这里是 [-1, -1]）。如果是初始值，说明没有待下传的任务，直接返回。”
“还有 _merge_val 方法，合并左右儿子的信息时，sum_min 和 sum_max 直接相加，因为要统计总和；l_min 和 l_max 取左儿子的值——注意：这里有个前提——只有在区间被统一赋值时，l_min/l_max 才有意义，合并时实际上只用叶子节点的真实值。”
我盯着那段 find_last 的代码，感觉脑子快要烧了：“这个 find_last 为什么优先查右子树？”
“因为要找’最后一个’满足条件的位置。“老勇者解释道，“线段树的中序遍历是从左到右，所以右子树的下标更大。优先查右子树，如果右子树里有满足条件的，就直接返回；如果没有，再查左子树。这样保证找到的是最右边的那个。另外，注意看它开头的判断：if l > qr or r < ql or not f(self._tree[node].val) 。如果当前节点的 val 都不满足条件 f，那它的子节点肯定也不满足，直接剪枝返回 -1。这是线段树查询的经典优化。”
接着，他写下了主逻辑：
# Lazy 线段树
t = LazySegmentTree(n)
cnt = s = 0
for i, x in enumerate(nums):
t.update(left_less_eq[i] + 1, i, (x, -1)) # 更新最小值
t.update(left_great_eq[i] + 1, i, (-1, x)) # 更新最大值
# 找到最后一个使得 最大值-最小值 >= low_d 的左端点
l = t.find_last(0, i, lambda v: v[3] - v[2] >= low_d)
if l >= 0:
cnt += l + 1 # 有 l+1 个子数组满足条件
d = t.query(0, l) # 查询这些子数组的 sum_min 和 sum_max
s += d[1] - d[0] # 极差之和 = sum_max - sum_min
return s - (cnt - k) * low_d # 减掉多算的
“这就是全部流程。“老勇者一边写一边解释，“每次 i 往右移一位，先用单调栈确定地盘，再用线段树做两次区间赋值——把 (left_less_eq[i], i] 的最小值刷成 nums[i]，把(left_greater_eq[i], i] 的最大值刷成 nums[i]。更新完之后，在线段树上用 find_last 在区间 [0, i] 内从右往左找到最后一个满足最大值 - 最小值 ≥ low_d的左端点 l。”
他顿了顿，补了一句："find_last 就是线段树上做一次二分——从右往左找最后一个满足条件的叶子位置。因为极差随左端点左移单调不减，区间越长，极差越大，所以找到最后一个过线的左端点 l，[0, l] 内的就全过线了。直接区间查询 [0, l] 的 sum_max - sum_min，累加进答案 s，数量 cnt 累加 l+1。最后，二分阶段确定的 low_d 是第 k 大极差，实际统计的过线数量 cnt 可能超过 k，多出来的那些极差都等于 low_d，答案减去 (cnt - k) * low_d 收工。”
终章：封印解除
我瘫在椅子上，盯着那张画满二叉树、懒标记和单调栈的草稿纸，感觉自己的脑细胞像被矿脉采掘过一样，空了又满，满了又空。
“让我理一理……” 我扶着额头，把刚才那一整套流程在脑子里重新串了一遍：”
- 二分答案：定位第 k 大的极差值
low_d，把选择问题降维成判定问题——我不需要知道具体是哪 k 个子数组，只需要知道第 k 大的极差是多少 - 滑动窗口 + 单调队列：在 check 函数里统计极差 ≥ X 的子数组数量，用双端队列维护窗口的最大最小值，O(n) 完成判定
- 单调栈预处理：给每个元素划好地盘，确定每个元素作为最小值/最大值的影响范围——left_less_eq 和 left_great_eq 就是它们的地契
- 懒标记线段树：动态维护每个左端点对应的子数组的极值，快速统计过线子数组的极差之和——区间赋值用懒标记 O(log n)，区间查询直接报总数 O(log n)”
老勇者欣慰地点点头，像是在看一个终于学会走路的孩子：“现在你来算算复杂度——”
“二分答案 O(log(max_val))，每次 check O(n)，单调栈 O(n)，线段树 O(n log n)。总复杂度 O(n log n + n log(max_val))，跟 k 无关！”
“这是真正的优化。“老勇者缓缓地站起身，火光映射下，他的身影就像超人一样，“昨天的堆 + 稀疏表，复杂度跟 k 线性相关；今天的二分答案 + 线段树，完全摆脱了 k 的束缚。当 k 很大时，这就是降维打击。”
“不过——” 他的话音严肃了起来，“今天的解法虽然复杂度更优，但代码量是昨天的三倍，调试难度也是指数级上升。在实际面试中，除非面试官明确要求’优化掉 k’，否则昨天的堆版本就足够了。别为了炫技把自己坑了。”
我目送老勇者的背影消失在村口，然后低头看了看草稿纸上那密密麻麻的四重封印——二分答案、滑动窗口、单调栈、线段树，每一个单独拎出来都能撑起一道中等难度的题，今天它们被串成一条流水线，就为了从一个十万长度的数组里精准捞出前 k 大极差。
炫技？我连把这套代码完整写出来不报错都够呛，还炫技。脑细胞都快集体罢工了好吧。
我小心翼翼地把画满老勇者笔迹的草稿纸收进我的魔法书里，想起老勇者的话，在旁边加了一小行：能用一行流解决的问题，别上 DP；能用堆解决的问题，别上线段树。但如果约束真的逼到了那一步——也别怂，四重封印该解就解，大不了多薅些头发。
本作品采用
知识共享署名-非商业性使用-禁止演绎 4.0 国际许可协议
进行许可。