# 地精排序题解

**出题人解法：逆序对计数与前缀最小值次数。** Codex（GPT-6）整理字典序比较、归并实现、64 位计数与证明。标程保留归并排序求逆序对的方案。

## 计数公式

令 $I$ 为输入向量序列的逆序对数。令 $R$ 为严格前缀最小值的次数：第一个向量计一次，之后每遇到比前面所有向量都小的向量，再计一次。

每次交换一对逆序的相邻向量，恰好消去一个逆序对。因此地精恰好交换 $I$ 次，也就是向左移动 $I$ 次。整个过程中从格子 $1$ 走到格子 $n$ ，向右移动总次数为 $I+n-1$ .

步骤 `(0)` 的向右移动恰有 $R$ 次。第一次从格子 $1$ 出发；之后，一个新访问的向量能够一路交换到第一个格子，当且仅当它是严格前缀最小值。处理后的前缀有序，已访问过的向量不会再次形成新的这种回退。

所有向左移动都对应一次成功的步骤 `(1)` 检查。所有向右移动之后会有一次步骤 `(1)` 检查，其中步骤 `(0)` 带来的回移不对应此前的失败检查，其余右移各对应一次失败检查；终点还有一次失败检查。因此失败检查次数为 $I+n-R$ ，总次数为

$$\boxed{2I+n-R}$$

等价地，可以把消去逆序所需的左右步数与从首格走到末格的移动合计，再扣除步骤 `(0)` 的特殊右移，补入末格的结束检查。

![向量退回到前缀正确位置的两次相邻交换](assets/gnome-swaps.svg)

图中数字表示向量的字典序名次，圈出的格子表示当前位置。两次成功检查各消去一个逆序对；到达第一个格子后，下一次移动执行步骤 `(0)` .

## 实现与正确性

先扫描输入计算 $R$ ，比较必须先看第一维，再看第二维，不能比较坐标和。然后归并排序求 $I$ ：右半区的当前向量小于左半区当前向量时，它和左半区尚未取出的所有向量构成逆序对，累加剩余数量。

归并计数包含每个逆序对恰好一次；前缀扫描准确计算严格最小值的次数；移动计数证明将这两个量转化为步骤 `(1)` 的执行次数，所以公式给出所求答案。输入保证向量互异，一维相等仍必须比较另一维。

## 复杂度与其他计数方法

时间 $O(n\log n)$ 、空间 $O(n)$ .答案可能超过 32 位整数，使用 64 位整数。

原材料还给出离散化后使用树状数组的计数方案，同为 $O(n\log n)$ 时间、$O(n)$ 空间。按向量字典序得到排名，顺序扫描并查询前面较大排名的数量，仍求得相同的 $I$ .该方案需要排名与树状数组；归并方案直接处理向量，因此作为标程。它们没有渐进复杂度差异，不据此宣称其中一种一定更快。

## 补充解法

排名后顺序扫描，用树状数组统计此前更大排名的数量，得到同一个逆序对总数。其时间 $O(n\log n)$ 、空间 $O(n)$ 与归并方案相同；计算结构不同，需要额外保存排名，作为并列方案完整交付。

[完整题解与测量](solution-alternative-fenwick.zh.md) · [计算程序](alternative-fenwick.cpp)