企业官网建设流程全解析

看到这个题号，很多刷题的老哥应该都不陌生。1618这道“排牌牌”，名字起得挺有生活气息，仿佛就是打牌的时候把乱牌一张张捋顺。但等你真上手写代码，就会发现这题根本不是让你模拟“捋牌”，它考的是你能不能把一个看似模拟的过程，看穿成离散数学里的经典量——逆序对。这篇文章不打算只贴一份AC代码就完事，我会从题目背后的逻辑开始讲，把为什么答案是逆序对数、归并排序怎么数、树状数组怎么数、以及我实际提交时踩过的坑全部摊开说，适合刚接触逆序对的初学者，也适合想彻底搞懂“相邻交换排序”这类模型的同学。

1. 先看懂“排牌牌”在问什么

1.1 题面到底长什么样

我没法保证每个OJ上的题面一字不差，但核心规则通常是这样的：有N张牌，牌面上写着1到N这N个数字，因为洗牌洗得比较狠，所以数字整体是乱的。现在定义一次操作：挑任意两张相邻的牌，交换它们的位置。问最少需要多少次操作，才能让所有牌从左到右按数字从小到大排好。

注意几个关键词：相邻交换、升序排列、最小次数。这三个条件叠在一起，基本就能锁定考点了。如果题目说“可以交换任意两张牌”，那是另一个模型，后面我会展开讲。这里说的“排牌牌”，绝大多数版本就是相邻交换。N的范围我没有必要瞎编一个精确值，但这类题给到1e5甚至1e6都很正常，反正直接模拟一定过不了。

我第一次看到这题的时候，脑子里第一个想法就是冒泡排序：从左往右扫，遇到逆序就交换，顺便计数，扫到没有逆序为止。对小数据这当然没问题，可一旦N是十万量级，O(N^2)的冒泡就是灾难，1e10量级的操作，在1秒时限下完全没有生还的可能。所以这题一定不是让你去真的“排牌”，而是要你找到某个能直接计算出答案的数学量。

1.2 关键观察：相邻交换能改变什么

让我们把问题抽象一下。给定一个排列，也就是一个长度为N的数组，目标是从小到大有序。定义“逆序对”为一对下标i<j、但a[i]>a[j]的位置。在升序排列里，逆序对数量是0；一个完全降序的排列，逆序对数量最大，是N*(N-1)/2。

现在看一次相邻交换到底会产生什么影响。假设我们要交换位置k和k+1上的两个数，也就是相邻的两个元素。交换之后，这两个数和它们前后所有元素之间的相对位置关系其实都没变，变的只是这两个元素之间的先后顺序。如果原来a[k]>a[k+1]，这两个元素构成一个逆序对，交换后它们变成有序，逆序对数量减少1。如果原来a[k]<a[k+1]，交换后逆序对数量反而增加1。

也就是说，任何一次相邻交换，最多只能让整体逆序对数量减少1。而我们的目标状态逆序对数量是0，所以从初始状态到目标状态，至少需要初始逆序对数那么多次操作。这个下界能不能达到？能。只要序列还没完全升序，就必然存在至少一对相邻的逆序对，因为如果所有相邻位置都升序，整个序列就升序了。那么我们每次都找一对相邻逆序对交换，每步都能让逆序对数量减1，一直减到0为止。所以“最少操作次数=初始逆序对数量”这个结论，就是从这两个方向夹出来的。

这个推导过程建议大家自己动手写一遍，哪怕是用小例子，比如[3,1,2]或[2,3,1]，逐个画一下交换过程，体会一次交换只影响一对相邻元素这件事。想清楚这一层，题目就从“模拟题”变成了“计数题”。

2. 怎么数逆序对：归并排序与树状数组

2.1 归并排序求逆序对的原理

既然答案是逆序对数，接下来问题就变成：怎么在O(N log N)时间内数出逆序对。最常见的做法是归并排序。它的核心思想是分治：把数组从中间分成左右两半，分别递归求出左半内部的逆序对数、右半内部的逆序对数，然后在合并左右两半的时候，数出所有“横跨左右”的逆序对。

合并过程本身就是把两个已经有序的子数组合并成一个有序数组。假设左半边从i到mid，右半边从j到r。当右半边的当前元素a[j]小于左半边的当前元素a[i]时，这里就产生了一大批逆序对：因为左右两半各自有序，左半边从i到mid的所有元素，全都比a[j]大，而且它们在原数组里的位置都在a[j]之前。因此逆序对数量要加上(mid-i+1)。反过来，如果左半边的a[i]小于等于右半边的a[j]，则没有逆序对产生，直接照常放入合并数组。

在代码层面，归并排序统计逆序对特别自然，只需要在“取右半边元素”的那个分支里加一句计数就行。我直接把常用模板贴出来，注释都写清楚，方便对着看。

#include <bits/stdc++.h> using namespace std; int n; int a[100005]; int tmp[100005]; long long ans = 0; // 答案必须是 long long void mergeSort(int l, int r) { if (l >= r) return; int mid = (l + r) >> 1; mergeSort(l, mid); mergeSort(mid + 1, r); int i = l, j = mid + 1, k = l; while (i <= mid && j <= r) { if (a[i] <= a[j]) { tmp[k++] = a[i++]; } else { // a[j] 比 a[i] 小，说明左半边从 i 到 mid 都和 a[j] 构成逆序对 tmp[k++] = a[j++]; ans += (long long)(mid - i + 1); } } while (i <= mid) tmp[k++] = a[i++]; while (j <= r) tmp[k++] = a[j++]; for (int p = l; p <= r; ++p) { a[p] = tmp[p]; } } int main() { scanf("%d", &n); for (int i = 1; i <= n; ++i) { scanf("%d", &a[i]); } mergeSort(1, n); printf("%lld\n", ans); return 0; }

关于“a[i] <= a[j]”这个判断，有个细节：要不要取等号。如果题目规定牌面是1到N的排列，没有重复数字，取不取等号其实不影响计数，因为相等的情况不存在。但如果你在练习题或变体里遇到有重复值的序列，那么等于的情况一定不能算作逆序对。使用<=，等于时优先取左半边的元素，能保证统计不漏也不多。从稳定性角度说，归并排序本身是一个稳定排序，用<=是符合稳定排序语义的。

2.2 树状数组求逆序对的思路

另一个高效方案是树状数组。它的思路比归并排序更接近“计数”本身：我们不看元素大小，而是把数组当成一个桶，统计每个数值已经出现了多少次。

假设我们从右往左扫描原数组。对于当前扫到的元素x，所有已经扫过的元素都在x的右边。如果其中有些元素比x小，那么它们和x就能构成逆序对。于是只要查询一下“数值区间[1, x-1]里已经插入了多少个数”，再把这个数量累加到答案里，然后把x也插入桶中。这个过程用树状数组可以做到单次操作O(log N)，总体O(N log N)。

那为什么需要离散化？因为如果牌面上的数字范围很大，比如大到1e9，我们不可能开一个1e9大小的数组。离散化的思想是：把所有数字排序并去重，然后用数字在排序数组中的排名来代表它本身。这样值域被压缩到N以内，树状数组的下标就够用了。

#include <bits/stdc++.h> using namespace std; const int MAXN = 100005; int n; int a[MAXN]; int c[MAXN]; vector<int> sorted; int lowbit(int x) { return x & (-x); } void add(int p, int v) { for (; p <= n; p += lowbit(p)) { c[p] += v; } } int query(int p) { int res = 0; for (; p > 0; p -= lowbit(p)) { res += c[p]; } return res; } int main() { scanf("%d", &n); for (int i = 1; i <= n; ++i) { scanf("%d", &a[i]); sorted.push_back(a[i]); } sort(sorted.begin(), sorted.end()); sorted.erase(unique(sorted.begin(), sorted.end()), sorted.end()); for (int i = 1; i <= n; ++i) { a[i] = lower_bound(sorted.begin(), sorted.end(), a[i]) - sorted.begin() + 1; } long long ans = 0; for (int i = n; i >= 1; --i) { ans += query(a[i] - 1); add(a[i], 1); } printf("%lld\n", ans); return 0; }

这段代码里最容易被忽略的是离散化后的下标从1开始。tree数组天然要求下标从1起，否则add和query里的lowbit循环会出问题。lower_bound返回的是0-based下标，一定要加1。这个+1，我见过的初学同学里至少有一半会在这里WA一次，包括我自己当年也是，提交上去错得莫名其妙，半天才发现下标越界或查询范围不对。后面我专门列一个踩坑清单。

2.3 归并排序和树状数组怎么选

很多同学会纠结：这两种都能过，到底写哪种好？我直接给结论：看数据范围和你的熟练度。

归并排序的好处是不用考虑值域，数组多大都能跑，而且分治过程天然稳定，对重复元素的处理很直观。缺点是代码量稍长，而且它是递归的，如果你是那种写递归容易晕的人，调试起来可能费点劲。树状数组的代码量更短，逻辑更“在线”，一旦你会背模板，写起来非常快。但它的前提是要做离散化，而且如果题目数据里有重复值，你需要想清楚查询范围是query(a[i]-1)还是query(n)-query(a[i])，两个方向都能得到正确答案，但写错一个就全盘皆输。

从运行常数来说，归并排序通常比树状数组快一些，因为树状数组每次查询和修改都要走一遍lowbit路线，常数比较大。不过在1e5量级，这点差距完全感知不到；到了1e6量级，两者也都还能压进时限。我的习惯是：如果这道题我还要顺手复现一下稳定排序，就写归并；如果只是想快速交掉，就写树状数组。两种都练熟，以后遇到逆序对变体才不会慌。

3. 从“排牌牌”往外看：不同玩法对应不同结论

3.1 看清操作类型比背结论重要

“排牌牌”这类题最大的迷惑性在于名字太像模拟，以至于很多人一上来就手写冒泡。其实排序类问题的算法选择，几乎完全由“操作类型”决定。操作类型一变，答案模型就完全不一样。

如果操作是交换相邻元素，最小次数等于逆序对数。这正是本题。如果操作是交换任意两张牌，结论就变成了N减去置换环的个数。如果操作是抽出一张牌再插入到任意位置，结论又变成了N减去最长上升子序列长度。

为什么相邻交换对应逆序对？因为一次相邻交换只改变一对元素的相对顺序，等于每次只能消除一个逆序对。而任意交换为什么对应置换环？因为你可以把任意两个位置的数直接互换，那么一个长度为k的置换环内部，只需要k-1次交换就能全部归位。抽出插入为什么对应最长上升子序列？因为不动的牌必须保持原有相对顺序，而且数值要递增，能够“原地不动”的最多那批牌，恰好就是原序列中的一个最长上升子序列。

3.2 举个小例子感受置换环模型

假设数组是[2,3,1]，目标升序是[1,2,3]。如果允许任意交换，那么2应该在位置2，3应该在位置3，1应该在位置1。把每个元素当前所在位置映射到它应该去的位置，会得到一个环：位置1上的2要去位置2，位置2上的3要去位置3，位置3上的1要去位置1，这三个位置构成一个三元素环。一个长度为k的环，只需要k-1次交换就能恢复，所以这个例子需要2次交换。你可以试一试，确实两次就能排好。

再比如[2,1,4,3]，它有两个二元素环，每个环需要1次交换，总共2次。这就是“N减置换环数”的含义：每个长度为k的环只需要k-1次操作，把N个元素所在的环加起来，就是N减去环的个数。

3.3 再看抽出插入模型

如果操作是“抽一张牌出来，插入到任意位置”，那你想想看：哪些牌可以完全不动？它们在被抽插的过程中保持相对位置不变，并且最终必须有序，所以它们在原序列里本身就是按数值递增的相对顺序出现的。这正好是LIS的定义。假设原序列是[3,1,2,4]，LIS是[1,2,4]或[1,2,3]，长度为3，那么把3拿出来插到末尾，一步就排好了。答案就是N-LIS。

很多同学刷题久了容易把结论背死，看到“最小交换次数”就套逆序对。这里我真心建议：每碰到一道题，先圈出“每次操作可以做哪件事”，再决定套哪个模型。三步走：先把操作翻译成数学变化，再想这个变化量每步最多能减少多少，最后找数据结构实现计数。这个方法能覆盖一大类排序问题。

4. 完整AC代码与提交时的细节

4.1 归并排序版本完整程序

把代码放一起，方便直接复制调试。要注意的就是数组大小一定开够，下标从1开始。如果题目数据到1e6，数组还要再开大一点，不能刚好卡在1e5。

#include <bits/stdc++.h> using namespace std; const int MAXN = 100005; int n; int a[MAXN], tmp[MAXN]; long long ans; void mergeSort(int l, int r) { if (l >= r) return; int mid = (l + r) >> 1; mergeSort(l, mid); mergeSort(mid + 1, r); int i = l, j = mid + 1, k = l; while (i <= mid && j <= r) { if (a[i] <= a[j]) { tmp[k++] = a[i++]; } else { tmp[k++] = a[j++]; ans += (long long)(mid - i + 1); } } while (i <= mid) tmp[k++] = a[i++]; while (j <= r) tmp[k++] = a[j++]; for (int p = l; p <= r; ++p) { a[p] = tmp[p]; } } int main() { while (scanf("%d", &n) != EOF) { for (int i = 1; i <= n; ++i) { scanf("%d", &a[i]); } ans = 0; mergeSort(1, n); printf("%lld\n", ans); } return 0; }

这个版本支持多组输入，每次循环前把ans清零。递归函数里没有依赖全局状态的坑，所以多组数据也能直接跑。如果你的OJ一次性只给一组数据，那while循环也无妨，多组数据时反而省心，不会因为忘记清空答案而WA。

4.2 树状数组版本完整程序

树状数组版本我也再给一份比较完整的。离散化的部分我和上面写的一样，放在main里。这里有个小优化：如果原题明确说了牌面是1到N的排列，离散化那一段其实可以省掉，因为值域已经天然是N了，直接a[i]当下标就行。但写通版总没有坏处，遇到值域大的题也能直接套。

#include <bits/stdc++.h> using namespace std; const int MAXN = 100005; int n; int a[MAXN]; int tree[MAXN]; int lowbit(int x) { return x & (-x); } void add(int p, int v) { for (int i = p; i <= n; i += lowbit(i)) { tree[i] += v; } } int sum(int p) { int res = 0; for (int i = p; i > 0; i -= lowbit(i)) { res += tree[i]; } return res; } int main() { scanf("%d", &n); vector<int> sorted; for (int i = 1; i <= n; ++i) { scanf("%d", &a[i]); sorted.push_back(a[i]); } sort(sorted.begin(), sorted.end()); sorted.erase(unique(sorted.begin(), sorted.end()), sorted.end()); for (int i = 1; i <= n; ++i) { a[i] = lower_bound(sorted.begin(), sorted.end(), a[i]) - sorted.begin() + 1; } long long ans = 0; for (int i = n; i >= 1; --i) { ans += sum(a[i] - 1); add(a[i], 1); } printf("%lld\n", ans); return 0; }

在main里先离散化再循环，是最清晰的结构。如果数据有重复且离散化后排名相同，树状数组的count会累积，但查询a[i]-1已经把等于自己的排除掉了，所以不会把相等元素误算成逆序对。这也是我为什么推荐“从右往左扫”这个写法，它天然只统计比当前严格小的元素。

4.3 提交时的IO和编译细节

这类数据量大的题，输入输出优化是必须的。用scanf/printf是一套稳妥方案；如果你非要用cin/cout，记得在main第一行写上ios::sync_with_stdio(false); cin.tie(nullptr);，不然很容易因为IO太慢被卡掉。有人说现在很多OJ的cin加了这两句话也很快，但牵涉到竞赛环境，我建议还是养成习惯，直接用scanf最保险。

还有一个细节：有些同学在本地用Dev-C++或某个旧编译器，long long可能在某些平台被写作__int64。现在的在线OJ基本都支持标准C++11或更新标准，直接写long long就行。如果遇到编译报错，优先检查代码里是不是写了变量名冲突，比如定义了一个叫left的变量。

5. 常见问题与排查实录

5.1 答案溢出：int装不下逆序对

这道题最大的隐藏陷阱就是答案类型。N=1e5的时候，最大逆序对数接近50亿，远超int的约21亿上限。我第一次交就是直接int ans，结果小数据全对，一上大范围数据就输出负数或莫名其妙的值。排查方法很简单：先算一下理论上限。当N=1e5，N*(N-1)/2=4,999,950,000，这已经超过2^31-1了，所以统计变量、加法中间量、输出格式都得换成long long。

写归并排序时，mid - i + 1本身是int，但累加到ans时我习惯写(long long)(mid - i + 1)，以防某些编译器在极端情况下做整型加法时先溢出。养成这个习惯能省去很多查溢出的时间。

5.2 离散化下标从1开始，不然树状数组直接崩

树状数组的add和sum都是从下标1开始操作的。lower_bound返回的下标是0到n-1，如果你忘记了加1，会出现两个问题：一是a[i]=0时，sum(0)或add(0)会导致死循环或错误；二是查询区间整体偏小，答案算少。这个问题我在前面已经强调过一次，但值得再提，因为它真的非常常见。

排查方法：输出离散化后的数组看看，如果有0出现，那基本就是忘了加1。或者直接开一个断点看sum(a[i]-1)是不是比预期小。

5.3 归并排序统计条件什么时候取等号

还是那句话，牌面是排列你就随便，不会有相等；如果题目允许重复数字，就必须用<=。很多同学写归并排序习惯写if (a[i] < a[j])，这在普通排序里没问题，但在求逆序对时，遇到相等元素会把本来不构成逆序对的情况也统计进去。记住一句话：等于不是逆序，所以取左边元素时用<=，保证等于情况下优先把左边元素放进来，右边元素等到严格大于左边时再操作。

5.4 多组输入没清空状态

我前面给的归并版本是每次循环都ans=0。如果你写的是全局ans，但主函数里没有在每组数据开头重置，第二组数据就会把第一组的答案累加进去。树状数组也一样，tree数组要在一开始全置零，可以用memset(tree, 0, sizeof(tree))。最多见的报错形式就是：第一组样例输出正确，第二组开始莫名变大。

排查这个问题的笨办法，是在每组开头输出一个自定义分隔符或者打印一些中间值，先确认各组之间互相独立。当然，正规做法是养成好习惯，先看题目是否说“多组测试数据”，不管有没有，都写上重置逻辑，稳赚不赔。

5.5 样例过了却全WA，问题多半在读入方式

有时候样例实测通过，但提交直接WA，而且不是RE不是TLE，就是错。遇到这种情况我建议大家先检查读入。比如有没有可能牌面数字是0到N-1而不是1到N？有没有可能要求排成降序而不是升序？这两个问题在变体题里都出现过，你不仔细看题，默认按升序写，自然错一片。

读入顺序也是一个点。有的题给两行，一行N，一行N个牌面数字；有的题第一行直接给N和序列在同一行。用cin或scanf按格式读一般问题不大，但如果你手动拼接数据或者用了某种自定义快读，要格外小心EOF处理。

5.6 本地对拍：暴力验证模板

无论写归并还是树状数组，强烈建议养成对拍的习惯。自己写一个暴力函数，双层循环统计逆序对，然后生成随机小数据，把暴力程序的结果和优化程序的结果对比。比如生成一个N=100的随机排列，用暴力双循环算一次，再用归并或树状数组跑一次，输出不一致就说明代码有隐蔽bug。

对拍听起来麻烦，其实能救大命。我印象最深的一次，就是树状数组从前往后扫的版本写成了sum(n) - sum(a[i])，小数据因为值域小碰巧对，一到大值域就翻车。没有对拍工具的话，这类边界问题很难定位。

5.7 超时了先别急着上优化，先看循环里有没有写错

如果TLE，先确认自己的算法确实是O(N log N)。有些同学写完归并在合并函数里又套了一个循环找逆序对位置，复杂度直接变成O(N^2)，那就不如不优化。还有一种常见情况是树状数组的add循环写了for (int i = p; i <= n; i += i & (-i))，这里记得用lowbit函数，别把i & (-i)写反。树状数组虽然简单，但lowbit表达式错了，最直接的后果是死循环或者更新位置不对。

TLE的排查思路：先跑一个极限数据，看本地运行耗时。1e5的数据，O(N log N)应该远小于1秒；如果你本地跑了超过两秒，说明实现里可能藏了额外的高复杂度操作，仔细检查每一个循环。

6. 做题方法论：从“排牌牌”到一类问题

6.1 最小操作次数类问题的三板斧

刷题多了你就会发现，“排牌牌”不是孤例，它代表了一整类“最小操作次数使序列有序”的问题。这类题的通用解法就是先定义一次操作会如何改变某个统计量。相邻交换改变逆序对数量，任意交换改变的是置换结构，抽出插入改变的是LIS长度。每换一种操作，统计量就换一个，背后的数据结构和算法也对应换掉。

所以以后再看到“最小操作次数”“相邻交换”“任意交换”“调整顺序”这些关键词，脑子里应该立刻弹出对应的候选结论。先别急着写代码，先把操作翻译成数学模型。这一步通常决定了你能不能AC，而不是最后代码写得漂不漂亮。

6.2 把模拟操作数学化，是第一步

我在教朋友时经常说一句话：看到排序类操作，先想“一步最多能消除多少乱序”。相邻交换一步最多消除一个逆序对，这就是下界；通过反复交换相邻逆序对又能达到下界，这就是最优性证明。同样，任意交换一步最多让一个元素归位吗？其实不是，但它可以每步把一个环的大小减少1，所以总代价和环长相关。抽出插入一步可以让一个元素移动到任意位置，那不动点越多越好，于是LIS就自然浮现。

这种“先证下界，再构造达到下界的方案”的思考方式，是很多算法题的通用钥匙。哪怕不是为了竞赛，平时写程序时遇到“最少步骤”的需求，也值得先想一想，别急着暴力模拟。

6.3 刷题经验什么时候能复用

很多人刷题是刷一道忘一道，看到新题又开始直觉模拟。我的经验是，不仅要记住结论，还要记住结论的前提。比如逆序对模型成立的前提是“只能交换相邻元素”；一旦题目说“可以交换任意相邻的一段”之类的加强操作，逆序对结论就可能失效。学会抽象问题、而不是背题，才能真正提高。

我自己的练习习惯是：每AC一道题，就在代码旁边写一行注释，记录这个题属于哪个模型、用了什么数据结构、时间复杂度多少。日积月累，再看到新题，模型匹配速度会快很多。这道1618排牌牌就是一个特别典型的“入门逆序对”标记点，吃透它的每一步，比AC它本身更有价值。

最后再分享一个实战里的小技巧。如果你在考试或比赛中一眼认出这是逆序对题，但时间紧张，不想写归并也不想写树状数组，可以赌一下数据范围，用分块之类的方法也能过，代价是代码更复杂。更稳的做法其实是平时就把归并排序和树状数组两份模板都背得滚瓜烂熟，遇到这题直接默写，一分钟都不浪费。我后来参加模拟赛时，遇到逆序对题基本不犹豫，直接在归并排序的else分支里加一行计数，这行已经成了肌肉记忆。希望这篇题解能让你也早日形成这种肌肉记忆。