拼多多 10 月 11 日机考笔试两题：水箱相邻指令对调数与测温区间最长段

《面试题目》

1. 第 1 题「水箱指令对调数」：水箱容量上限为 V，开机时水位为 s。操作清单上按顺序记有 m 条指令，第 i 条是整数 d_i：d_i > 0 表示注入 d_i 单位水，d_i < 0 表示排出 -d_i 单位水，d_i = 0 表示只做水位核对、水位不变。执行时把指令数值累加到当前水位，称一次完整执行安全，意思是任意前缀执行完后水位始终落在闭区间 [0, V] 内（可以贴边但不能越界）。实验员抄单时一定会把某一处相邻两条指令的次序抄反，对每个下标 i（1 ≤ i < m），考虑交换第 i 条与第 i+1 条后按新顺序执行全部指令，请统计有多少个下标 i 使得交换后的执行过程仍然安全。注意：必须恰好交换一对相邻指令，原顺序本身不计入；即使 d_i = d_{i+1}，下标 i 仍然是合法的抄反位置，交换后若安全则计入；m = 1 时不存在相邻对，答案为 0。输入第一行是整数 m，第二行是整数 V，第三行是整数 s，第四行是 m 个整数 d_1 到 d_m；输出一个整数，表示满足条件的相邻交换位置数量。

2. 第 2 题「测温共值最长段」：机房按天记录机柜温度，第 i 天的读数是一个闭区间 [a_i, b_i]，表示真实温度（取整数刻度）可能落在该区间内，共 m 天且按日期先后排列。需要选出一段非空的连续日期，下标记为 [p, q]；在这段日期中允许至多把一天的记录当作故障丢弃，也可以一天都不丢，丢弃后至少要留下一天记录，并且存在一个整数 t 落在每一条保留记录的闭区间内——也就是说未丢弃的那些天里真实温度都有可能取同一个整数 t。所选连续段的跨度定义为 q - p + 1，被丢弃的那一天仍然计入跨度，请给出合法跨度的最大值。输入第一行是整数 m，第二行是 m 个整数 a_1 到 a_m，第三行是 m 个整数 b_1 到 b_m；输出一个整数，表示合法连续段的最大跨度。

《参考解析》

第 1 题：交换相邻两条指令，只会动到一个前缀

题面里那句「必须恰好交换一对相邻指令」是本题的钥匙，它把需要判断的位置从任意交换压到 m-1 个，也把每次判断的代价从重新模拟的 O(m) 压到 O(1)。

设原序列执行完前 j 条指令后的水位为 P_j = s + sum(d_k, k = 1..j)。交换第 i 条与第 i+1 条之后会发现三件事：前 i-1 个前缀的水位完全没有变；第 i 个前缀从 P_{i-1} + d_i 变成了 P_{i-1} + d_{i+1}；从第 i+1 个前缀开始，参与累加的仍然是同样那批指令，只是内部顺序变了，总和不变，所以全部回到原来的 P_j。换句话说，一次相邻交换只可能让一个前缀发生变化。

于是「交换后是否安全」被拆成两个互不干扰的条件：一是原序列里除了第 i 个前缀之外，其它前缀有没有越界；二是新算出来的那个前缀 P_{i-1} + d_{i+1} 有没有越界。做法就很直白了：先扫一遍原序列，数出越界前缀的总数 bad，同时记录每个前缀的值；再扫一遍每个交换位置 i，把 bad 减去「原第 i 个前缀是否越界」得到 otherBad，只要 otherBad == 0 且 0 ≤ P_{i-1} + d_{i+1} ≤ V，这个 i 就计入答案。两次线性遍历即可，O(m) 时间、O(m) 空间；如果用滚动变量边算边判，额外空间还能压到 O(1)。

有几个细节属于「不写出来就会被扣分」的。第一，被替换掉的那个前缀是老值 P_{i-1} + d_i，判断越界要减的是它的贡献，索引差一位整题就错了；写代码时维护一个变量表示「当前处理的这一对之前的水位」，每轮结束把它推进到 P_i，能天然避开这个 off-by-one。第二，d_i = d_{i+1} 的位置照样要计数——交换后序列和原序列一模一样，所以只要原序列本身安全，这些位置全部合法，答案可能因此变得很大，不能顺手跳过。第三，题面没有给 d_i 的取值范围，水位是会累加的，用 64 位整数存它，别赌 int 不溢出。第四，m = 1 时没有相邻对，答案固定为 0。反过来，如果按每个 i 都重新跑一遍模拟，复杂度是 O(m²)，在这个数据规模上必然超时，所以「一次交换只影响一个前缀」这句话必须主动讲出来。

第 2 题：把「丢一天」翻译成次大值与次小值

第二题的题面绕，先把它改写成人话：对窗口 [l, r]，要判断是否存在一个整数 t，使得窗口内至多只有一天的区间不包含 t；等价的说法是「这组区间的公共交集，在移除至多一个区间之后非空」。

记窗口内所有 a_i 的最大值为 A₁、次大值为 A₂，所有 b_i 的最小值为 B₁、次小值为 B₂。注意数值相同的元素来自不同日期，要重复计数，所以不能先塞进集合去重。窗口长度不超过 2 时一定合法——最多删到只剩一天，单个区间总是有整数可取。长度至少为 3 时，合法的充要条件是 A₂ ≤ B₁ 或者 A₁ ≤ B₂。

这个条件值得展开解释，因为面试官大概率会追问「为什么是这两个」。区间集合有公共整数点的判据是 max a ≤ min b，也就是 A₁ ≤ B₁；如果它本来成立，一天都不用删，而这时 A₂ ≤ A₁ ≤ B₁ 自动满足，所以已经被「或」的左边覆盖了。真正的麻烦是 A₁ > B₁：最大左端点和最小右端点打架，而且这两个值不可能来自同一天——同一天必然有 a_i ≤ b_i，所以它们必定出自两个不同的日期。这一点是本题的题眼：删掉其中任意一个，另一个都还在，于是只剩两条路。要么删掉贡献 A₁ 的那天，冲突消失的条件退化成 A₂ ≤ B₁；要么删掉贡献 B₁ 的那天，退化成 A₁ ≤ B₂。两条路都走不通，说明这扇窗口无论怎么删都凑不出公共温度，只能把左端点右移。

实现就是标准的滑动窗口配两个堆：大根堆按 a_i 维护左端点，小根堆按 b_i 维护右端点，堆里存 (值, 下标)，左端点右移时用下标做懒删除，把窗口外的元素弹掉。取「次大／次小」的手法要记牢：先暂时弹出堆顶、清掉过期元素、读新的堆顶，再把原来的堆顶放回去；漏掉放回这一步，就会把真正的候选值丢掉。窗口长度大于 2 时循环判定，不合法就 ++l，合法就更新答案。每个元素各进两个堆一次、过期后最多被弹出一次，左右指针各走 m 步，总复杂度 O(m log m)、空间 O(m)。

收尾时留一句追问的答案会更完整：「能不能做到 O(m)？」严格线性的写法要维护滑动窗口的次大值和次小值，而单调队列擅长给最值、给次值需要额外的结构，写起来容易出错；在本题的数据规模下 O(m log m) 完全够用，硬追线性属于给自己挖坑。

两道题共同考的东西

第 1 题的本质是「扰动是局部的」：一次相邻交换只让一个前缀发生变化，于是可以把「重新模拟一遍」换成「在预先算好的总账上做一次加减」。这类「先统计全量，再减去被替换项贡献」的套路在区间修改、滑动窗口、前缀和题目里反复出现，看到「交换一对」「改动一处」这类词就该条件反射地去找被影响的部分有多大。

第 2 题的本质是「把不好判的性质翻译成好判的判据」：合法性原本是「存在一个 t 被窗口内几乎所有区间覆盖」，直接枚举 t 是 O(V·m)；改写成「删掉一个区间后交集非空」，再落到次大值与次小值的比较，就变成 O(1) 判定。笔试里遇到自然语言描述很长的题，先花两分钟做这一步翻译，比立刻上手写代码划算得多。

两道题还有一个共同点：它们的指针都只往前走——前缀只前进一次、窗口左端点只右移。判断「指针会不会回头」往往是找到正解的最快路径：只要不回退，复杂度就落在线性或者带一个 log 的量级上。