地精排序题解¶
出题人解法：逆序对计数与前缀最小值次数。 Codex（GPT-6）整理字典序比较、归并实现、64 位计数与证明。标程保留归并排序求逆序对的方案。
计数公式¶
令 \(I\) 为输入向量序列的逆序对数。令 \(R\) 为严格前缀最小值的次数：第一个向量计一次，之后每遇到比前面所有向量都小的向量，再计一次。
每次交换一对逆序的相邻向量，恰好消去一个逆序对。因此地精恰好交换 \(I\) 次，也就是向左移动 \(I\) 次。整个过程中从格子 \(1\) 走到格子 \(n\) ，向右移动总次数为 \(I+n-1\) .
步骤 (0) 的向右移动恰有 \(R\) 次。第一次从格子 \(1\) 出发；之后，一个新访问的向量能够一路交换到第一个格子，当且仅当它是严格前缀最小值。处理后的前缀有序，已访问过的向量不会再次形成新的这种回退。
所有向左移动都对应一次成功的步骤 (1) 检查。所有向右移动之后会有一次步骤 (1) 检查，其中步骤 (0) 带来的回移不对应此前的失败检查，其余右移各对应一次失败检查；终点还有一次失败检查。因此失败检查次数为 \(I+n-R\) ，总次数为
等价地，可以把消去逆序所需的左右步数与从首格走到末格的移动合计，再扣除步骤 (0) 的特殊右移，补入末格的结束检查。
图中数字表示向量的字典序名次，圈出的格子表示当前位置。两次成功检查各消去一个逆序对；到达第一个格子后，下一次移动执行步骤 (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)\) 与归并方案相同；计算结构不同，需要额外保存排名，作为并列方案完整交付。