# 地精排序：离散化与树状数组

**出题人解法：向量排名、树状数组逆序对计数与前缀最小值次数。** Codex（GPT-6）补齐此方案的证明与 C++17 [计算程序](alternative-fenwick.cpp)。它与[归并计数](solution.zh.md)同阶，使用不同的数据结构，两者并列介绍，归并方案仍作标程。

## 排名与顺序扫描

按二维向量的字典序排序，给每个向量唯一排名 $r_i$ ，并映射回其原始位置。第一维相同时仍按第二维排序；不能用坐标和代替字典序。互异保证排名没有并列。

按原输入顺序扫描。树状数组保存已经处理的每个排名的出现次数。处理第 $i$ 个向量前，数组中共有 $i-1$ 个向量，因此

$$d_i=(i-1)-\operatorname{Prefix}(r_i)$$

就是此前排名更大的向量数，恰为以当前位置为右端点的逆序对数。累加后再把当前排名加入树状数组，得到总逆序对数 $I=\sum_i d_i$ .

另一次扫描记录严格前缀最小值次数 $R$ ：第一个向量计一次，此后仅当向量比当前最小向量还小时计数。

## 从逆序对到检查次数

沿用主题解的移动计数证明：相邻交换恰好消去一个逆序对，所以成功检查有 $I$ 次；失败检查有 $I+n-R$ 次。两者合计

$$2I+n-R$$

树状数组给每个逆序对按其右端点计数且恰计一次，前缀扫描准确求出 $R$ ，因此结果正确。计数与最终答案使用 64 位整数。

## 复杂度与取舍

排序及树状数组操作共 $O(n\log n)$ 时间，向量、排名和树状数组共 $O(n)$ 空间。与归并计数的阶相同；此方案将计数转为扫描期间的前缀频次查询，更便于扩展到带插入的排名统计。代价是保存排名与额外数组，且必须先排序完成离散化。不能据同阶复杂度宣称哪种实现一定更快，当前完整范围的时间与空间见实测。

## 同输入测量

与标程在全部 10 份正式输入上的输出一致；五轮交替计时及输入、源码、程序哈希见[完整记录](../../../docs/benchmark-R14-supplements.json)，环境见[参考评测环境](../../../docs/评测环境与性能.md)。标程最慢中位耗时为 0.142160 秒，补充方案为 0.148444 秒；峰值工作集分别为 12.79 与 18.53 MiB，包含进程与运行库开销。
补充程序在全部已测正式输入上均低于 0.5 秒参考时限。该结论仅针对随附实现、这些输入与参考环境；有限测试不代替正确性证明，也不保证每一种同阶实现通过。