前几天在洛谷刷题单时看到了 P14899 这道题题名是 What Goes Up Must Come Down出处是 ICPC 2018 Yokohama Regional。名字取自“上山容易下山难”那句俏皮话但比赛题从来不会只有俏皮。题意很朴素给你一个序列每次可以交换相邻两个数问最少交换多少次能让整个序列变成“先单调不降、再单调不增”的山形。说白了就是左边上坡、右边下坡中间可以有一个平台。我第一反应这题应该和逆序对有关毕竟“最小相邻交换次数”这个说法太容易让人往冒泡排序上想结果一上手就发现不是那么回事。把这题的完整推导、树状数组实现和几个调试时踩过的坑整理成一篇希望能帮到正在补 ICPC 题单或者准备区域赛的朋友。1. 题目到底在问什么1.1 把题面翻译成人话输入一个长度为 N 的整数序列 h_1, h_2, ..., h_N。一次操作可以交换相邻两个数。目标是把整个序列变成“山形”存在一个位置或者一段连续区域它左边的部分是单调不降的右边的部分是单调不增的。注意是“不降”和“不增”所以相邻相等是合法的。峰顶也可以是一个平台比如 [1,2,2,3,3,2,1] 就满足条件。这里有一个很容易想歪的点题目并没有规定最大值必须出现在某个固定位置也没有规定山一定很“尖”。只要存在一个分界点使得前缀是上升段、后缀是下降段就行。所以 [1,2,3] 是合法的[3,2,1] 也是合法的[1,2,2] 合法[2,1,1] 也合法。理解清楚这一点后面建模才不会跑偏。数据范围我没有刻意背但这类区域赛题通常 N 会到 2e5 的量级值域可能到 1e9因此必须设计 O(N log N) 级别的算法不能依赖 O(N^2) 的暴力。1.2 “相邻交换的最少次数”到底在数什么相邻交换排序问题有一个非常经典的等价关系从序列 A 变成序列 B 的最少相邻交换次数等于把 A 中每个元素按 B 中的顺序重新编号后这个新序列的逆序对数量。逆序对数量代表“本来应该在前面的元素现在跑到后面去了”的对数而每次相邻交换恰好能修复一对这样的相对顺序错误。这个结论对“把 A 排序成升序”很直观因为排序后的最终顺序是固定的。但这题的问题在于最终的山形不固定每个元素周围的峰顶位置也完全未知所以不能直接套用逆序对模板。如果我们把所有合法山形都枚举出来再分别求一遍逆序对理论上能做但 N 很大时完全不可行。所以要找一个不需要枚举最终形态而是直接对每个元素单独计算贡献的方法。1.3 合法形态的“嵌套结构”山形序列有一个很明显的特点最小值一定在最外层。也就是说全局最小值要么出现在整个序列最左边要么出现在最右边绝不会藏在中间。因为如果最小值在中间那么它左边是上升段右边是下降段无论从左还是从右看它都不可能小于两边的所有元素矛盾。如果把这个最小值从序列中拿掉剩下部分依然是一个山形。继续看剩下的最小值它一定又出现在当前序列的两端之一。这个观察非常重要。它把“堆一座山”变成了“从外到里一层一层堆”的过程最外层放最小的数往里一层比一层大最中间是最大值。这也是题目名字“What Goes Up Must Come Down”背后的结构不只是字面意思而是整个序列存在一个由小到大、再由大到小的嵌套顺序。2. 核心观察从外到内把山搭起来2.1 最小的一批值一定在山脚假设现在所有数还没排好我们只看当前序列中数值最小的那个元素 x。根据上面的推论x 最终一定会被放到序列的最左端或者最右端。如果把它放到最左端它需要向左移动跨过所有原本在它左边、但还没确定位置且比它大的元素。如果把它放到最右端它需要向右移动跨过所有原本在它右边、但还没确定位置且比它大的元素。注意这里“比它大”是关键词。因为山形从左到右是先升后降所有比 x 大的元素都要排在 x 的“内侧”也就是右边如果 x 在最左或左边如果 x 在最右。所以说 x 移动时跨过的对象是比它大的数不是比它小的数。这一点和直觉相反但很关键。2.2 剥掉一层问题变成同构子问题处理完当前最小值 x 之后可以把 x 从“待考虑序列”中移除。剩下的数仍然要组成一个山形只是规模变小了。继续找当前最小值 y它同样只能放到当前序列的两端之一。这个过程可以一直持续下去直到所有数都被放到“山”上。每次放置一个元素时它只需要决定自己是往左跑还是往右跑决策量很小。我们不需要真的模拟这个“从外到内”的过程因为每个元素被处理时所有比它更小的元素都已经被移除了。此时该元素左侧剩下的元素一定都是比它大的数量正好等于“原始序列中该元素左侧比它大的元素个数”。同理右侧剩下的元素也一定都比它大数量等于“原始序列中该元素右侧比它大的元素个数”。换句话说如果按值从小到大逐个处理那么每个元素 x 的左侧剩余元素数就等于 leftGreater[x]右侧剩余元素数就等于 rightGreater[x]这两个值可以直接从原始序列静态统计出来并不需要动态维护一个“当前剩余序列”。2.3 每个数的代价只需要取 min某个元素 x 放在最左端付出的代价是 leftGreater[x]放在最右端付出的代价是 rightGreater[x]。因为它只能选一边最优的策略当然是选这两者中较小的那个。所以一个看起来很自然的公式出现了$$ ans \sum_{i1}^{N} \min\big(leftGreater[i],\ rightGreater[i]\big) $$这个公式不仅直观而且最后会证明它是严格的每个元素独立决策不会出现“我选了左端你也选了左端结果我们俩卡住了”的情况。因为山形本来就是从外到内嵌套的所有选择“放左端”的元素按值从小到大依次排在左半边所有选择“放右端”的元素按值从小到大依次排在右半边天然不会互相冲突。2.4 一句人话总结核心思路山形序列无法直接枚举最终形态但可以反过来问每个数到底应该被放到山脚的左边还是右边放到左边就要把左边所有比它大的数挤到内侧放到右边就要把右边所有比它大的数挤到内侧。两边代价取小所有数加起来就是最少交换次数。3. 为什么答案是 min(左边更大, 右边更大) 求和3.1 从“元素对”的角度再证明一次相邻交换次数可以看成“最终需要翻转多少对元素的相对顺序”。把任意两个元素拿出来假设它们的值分别是 a 和 b且 a b。如果较小的那个元素 a 最终被放在山的最左端那么 b 无论被放在哪里都会在 a 的右边所以这对元素的相对顺序不需要翻转。反过来如果 a 被放在最右端那么 b 只能在 a 的左边这对元素的相对顺序必须交换一次。也就是说每一对大小不同的元素是否需要交换完全由较小的那个元素最终放在哪一侧决定。而对于元素 x 来说所有比 x 大的元素中如果 x 选择放左端那么原本在 x 左侧的那些更大的元素必须翻转到 x 右侧数量正好是 leftGreater[x]如果 x 选择放右端那么原本在 x 右侧的那些更大的元素必须翻转到 x 左侧数量正好是 rightGreater[x]。因为每一对元素只会被较小的那个元素计数一次不会重复所以把每个元素取 min 后的贡献直接相加就是所有必须翻转的元素对的最少数量。这也正好等于最少相邻交换次数。这个证明比直觉推导更严谨也解释了为什么公式可以直接求和。3.2 相等的元素为什么不捣乱如果有两个元素相等比如两个 3那它们谁在左谁在右完全不影响山形的合法性。上升段允许相等下降段也允许相等峰顶平台更是可以堆一堆相等值。因此在数“左边更大的数”和“右边更大的数”时必须使用严格大于不能把相等的算进去。这给实现带来一个好处树状数组里维护的是值域上每个数的出现次数查询时如果要用“小于等于当前值”的数量再用总数减掉就可以自然排除掉相等元素。比如左侧更大 左侧所有元素数量 - 左侧小于等于当前值的数量这样相等元素不会计进来。3.3 手算几个例子验证我们用三组数据亲手算一遍。第一组[3, 1, 2]位置当前值左边更大右边更大min030001111122100答案 1。实际交换3 1 2 - 3 2 1一次搞定。合法山形是 [3,2,1]。第二组[3, 2, 1, 4]位置当前值左边更大右边更大min03010121112121134000答案 2。实际交换3 2 1 4 - 3 2 4 1 - 3 4 2 1两步后变成 [3,4,2,1]上升段是 3 4下降段是 4 2 1合法。第三组[5, 4, 1, 2, 3]位置当前值左边更大右边更大min0500014100212223221143200答案 3。实际交换过程5 4 1 2 3 - 5 4 2 1 3 - 5 4 2 3 1 - 5 4 3 2 1最终得到合法的纯下降序列 [5,4,3,2,1]。这三组数据基本覆盖了“选左”“选右”“峰顶在最边缘”三种情况公式表现都正常。4. 树状数组两遍扫描代码与实现细节4.1 为什么要离散化题目给的 h_i 可能很大到 1e9 也很正常但树状数组下标需要从 1 开始连续维护。所以第一步把所有出现过的值排序、去重然后用二分查找把每个数映射到 1 到 M 的区间内。M 最多是 N复杂度 O(N log N)。这一步对 Java、C 选手来说都很常规。注意去重后每个数拿到的 id 范围是 [1, M]把它当成树状数组的“等级”即可。比如某个数在所有数中从小到大排第 k 名那 id 就是 k。4.2 从左往右算左边更大的个数维护一个树状数组从左往右扫描原数组。扫描到位置 i 时树状数组里已经存了左侧所有数的出现次数。设当前值离散化后是 id查询 sum(id) 可以得到左侧小于等于当前值的个数左侧元素总数就是 i那么leftGreater i - sum(id)这个式子把左侧所有元素数量减去左侧小于等于当前值的数量剩下的就是左侧严格大于当前值的数量。查询完之后把当前值的出现次数在树状数组里加 1继续处理下一个位置。4.3 从右往左算右边更大的个数同理可以把树状数组清空再从右往左扫描。扫描到位置 i 时树状数组里存了右侧所有数的出现次数。右侧元素总数是 N - 1 - i查询 sum(id) 得到右侧小于等于当前值的个数那么rightGreater (N - 1 - i) - sum(id)这样得到的就是右侧严格大于当前值的个数。因为只需要两遍扫描整体时间复杂度 O(N log N)。空间上需要 O(N) 的树状数组和两个结果数组。4.4 完整 C 代码#include bits/stdc.h using namespace std; struct Fenwick { int n; vectorint c; Fenwick(int n 0) { init(n); } void init(int n_) { n n_; c.assign(n 1, 0); } void add(int i, int v) { for (; i n; i i -i) c[i] v; } int sum(int i) { int res 0; for (; i 0; i - i -i) res c[i]; return res; } }; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin n; vectorint h(n); for (int i 0; i n; i) cin h[i]; // 离散化 vectorint vals h; sort(vals.begin(), vals.end()); vals.erase(unique(vals.begin(), vals.end()), vals.end()); auto getId [](int x) { return int(lower_bound(vals.begin(), vals.end(), x) - vals.begin()) 1; }; int m vals.size(); Fenwick bit(m); vectorint leftGreater(n), rightGreater(n); // 从左往右左边更大的个数 for (int i 0; i n; i) { int id getId(h[i]); // i 是左侧元素总数sum(id) 是左侧 h[i] 的数量 leftGreater[i] i - bit.sum(id); bit.add(id, 1); } // 清空重来 bit.init(m); // 从右往左右边更大的个数 for (int i n - 1; i 0; i--) { int id getId(h[i]); // n - 1 - i 是右侧元素总数sum(id) 是右侧 h[i] 的数量 rightGreater[i] (n - 1 - i) - bit.sum(id); bit.add(id, 1); } long long ans 0; for (int i 0; i n; i) { ans min(leftGreater[i], rightGreater[i]); } cout ans \n; return 0; }4.5 复杂度分析和容易超时的点时间复杂度是两次 O(N log N)空间复杂度 O(N)。对于 N2e5这个复杂度非常安全。有一个小细节树状数组的 add 和 sum 函数里循环结束条件都是 i n 或 i 0。离散化后 id 一定在 [1, M] 范围内所以不会越界。要注意的是如果从右往左那遍忘记把树状数组重新 init那么右侧计数会把左侧结果也带进去答案会严重偏大。我排查过很多类似代码最常见的错误就是忘记第二次初始化。5. 常见错误、相等元素和对拍方法5.1 最容易错的地方方向用反我第一次做的时候条件反射算的是“左边更大的数量”和“右边更小的数量”也就是把两个方向搞反了。用 [3, 1, 2] 这个例子测一下就会发现答案算成 0但实际上最少需要 1 次交换。这里从头强调一遍元素 x 如果最终放在右边它需要跨过的是右边比它大的元素而不是比它小的元素。因为右半边是下降段大的元素在小的元素之前所以 x 想跑到右端就必须和右侧所有更大的元素交换。方向反了很多边界数据会直接出错。如果不想记左右方向可以换个思路无论 x 放左还是放右跨过的一律是“比它大的数”。这样就不会混了。5.2 等值元素的处理假如有一个序列 [2, 1, 2, 1, 2]两个 1 都要放到山脚。用公式算第一个 1左边更大 1右边更大 2取 min 1第二个 1左边更大 2右边更大 1取 min 1答案 2。实际可以这样构造2 1 2 1 2 - 1 2 2 1 2 - 1 2 2 2 1最后一步交换 1 和 2但 [1,2,2,2,1] 合法只需要 2 步原序列 2 1 2 1 2 先把第一个 1 往左跨过第一个 2得到 1 2 2 1 2 再把第二个 1 往右跨过最右边的 2得到 1 2 2 2 1。 两步。目标 [1,2,2,2,1] 是合法山形答案确实是 2。相等元素之间不用交换这个题在实现时用“严格大于”的统计方式自然就规避了等值产生的额外代价。5.3 对拍模板验证公式的最好方式如果你对自己写的公式没把握最直接的办法是写一个对小数据的暴力算法去对拍。一个可行的暴力做法对于 N 8 的小数据枚举原序列下一组排列或者用 DFS 做相邻交换判断是否满足山形然后求该排列与原序列之间的最小交换次数。求两个排列之间的最小相邻交换次数时可以把目标排列中每个元素映射回在原序列中的下标然后数逆序对数量。也可以用更简单的 BFS把每个序列看成一个状态每次交换相邻元素步长加一一旦出现合法山形就返回当前步数。N8 的时候状态数量可控足够对拍。随机生成几十组数据拿树状数组算法和暴力结果对比一旦方向反了立刻就能看出来。我这里没有写完整对拍代码因为不同选手习惯的暴力写法差别很大但核心逻辑就是“枚举最终排列 数逆序对”或者“BFS 搜相邻交换”。坚持对拍能省下大量改错时间。5.4 关于答案类型和输入输出的坑答案最大会是多少最坏情况是所有数从大到小排好右边更大都是 0左边更大分别接近 N取 min 后大概是每项 N/2 级别总和可能达到 2e5 * 1e5 量级也就是 2e10 左右。int 完全装不下必须开 long long。我在本地一开始定义成 int跑样例没问题但随手构造一组逆序数据就翻车了。所以提交前先想想答案上界不要等 WA 了再去排查。输入输出方面N 很大时建议关闭 C 输入输出同步否则 cin 读 2e5 个整数会有不必要的性能损耗。5.5 和普通逆序对题目的区分碰到“相邻交换最小次数”第一反应确实是逆序对。但这题不能直接统计全局逆序对因为最终山形有无数种可能每个元素不一定都按升序排列。更合适的理解是每个元素只需要决定自己放到山脚左边还是右边然后它和一侧更大元素之间的交换次数就是它的代价。如果题目改成“把序列变成单调不降”答案就是整个序列的逆序对数。这题是“先不降后不增”多了一个峰值点和左右方向的自由选择所以每个元素要单独决策。把这两个模型放在一起对比就能感受到这类题目的变化点在哪里。6. 一点体会和两个小技巧我自己做这道题时最大的教训就是不要被“相邻交换”四个字带着走。逆序对模型确实漂亮但它只适合目标序列本质是“全序排序”的问题一旦目标形态变成了山形、环形、双调形就要回到更底层的“每一对元素是否需要翻转”去思考。这里分享两个实战小技巧。第一个如果拿不准每个元素该算“左边更大”还是“右边更小”直接取一个长度只有 3 的样例比如 [3,1,2]套进公式看答案对不对。这种极限小样例能暴露大部分方向错误。第二个区域赛题单里的题目很多时候不需要一次就写出完美代码。先用暴力对拍把公式验证好再上树状数组优化这样即使中间想偏了也能在几分钟内纠回来。对拍不是浪费时间它是在帮你把脑子里的模型校准。这道题的结构非常经典把“从外到内”的思考方式练熟之后以后再遇到类似的山形、环形排列问题你至少能第一时间找到正确的切入方向。希望这篇题解能帮你少走一点弯路。
