逆序对
一、题目简述
核心要求
给定一个长度为n的正整数序列，统计其中逆序对的数目。逆序对的定义为：序列中满足 ai>aja_i > a_jai >aj 且 i<ji < ji<j 的有序对 (i,j)。
数据范围
* 序列长度：1 ≤ n ≤ 5×10^5
* 元素大小：每个数字不超过 10^9
二、样例解析
样例输入
样例输出
推导过程
我们可以逐个统计每个元素作为a_i时，后面比它小的元素数量（即贡献的逆序对数目）：
* 元素5（位置1）：后面比它小的元素有4、2、3、1 → 贡献4个
* 元素4（位置2）：后面比它小的元素有2、3、1 → 贡献3个
* 元素2（位置3）：后面比它小的元素有1 → 贡献1个
* 元素6（位置4）：后面比它小的元素有3、1 → 贡献2个
* 元素3（位置5）：后面比它小的元素有1 → 贡献1个
* 元素1（位置6）：后面无元素 → 贡献0个
将所有贡献相加：4+3+1+2+1=11，与样例输出一致。
三、解题思路
1. 暴力解法分析
暴力思路：使用双重循环枚举所有i < j的组合，判断 ai>aja_i > a_jai >aj 并计数。
* 时间复杂度：O(n²)
* 缺陷：当n=5×10^5时，操作次数约为2.5×10^11，远超过竞赛中1秒约10^8次操作的限制，必然超时，无法通过所有数据。
2. 正解算法选择与核心思想
正解选择**树状数组（Fenwick Tree）**结合排序映射的方法，核心思想是：
* 通过排序将数值大小关系转化为处理顺序，避免直接比较所有元素对
* 利用树状数组高效统计前缀和，快速计算每个元素贡献的逆序对数目
3. 分步解题逻辑
1. 元素存储：将每个元素的数值与原位置绑定为pair，保留位置信息
2. 排序映射：按数值从小到大排序（数值相同则原位置小的在前），这样从后往前遍历时，先处理数值更大的元素
3. 树状数组操作：
* 从后往前遍历排序后的元素，对于每个元素的原位置pos
* 查询树状数组中1~pos-1的元素数量：这部分是已处理的（数值更大的）元素中，原位置在当前元素之前的数量，即当前元素贡献的逆序对数目
* 将当前元素的原位置插入树状数组，供后续元素查询使用
4. 累加结果：将所有元素的贡献累加得到总逆序对数目
四、代码详解
* 作用：返回x的最低位1对应的数值，是树状数组更新和查询的核心，用于快速定位树状数组的节点
* 作用：单点更新，将树状数组中位置x的元素计数加1
* 逻辑：通过lowbit快速跳转到父节点，更新所有相关节点
* 作用：查询前缀和，返回1~x位置的元素总数
* 逻辑：通过lowbit快速跳转到子节点，累加所有相关节点的数值
* 对p数组排序，默认按pair的first（数值）升序、second（原位置）升序排列，确保数值小的在前，数值相同的原位置小的在前
* 初始化ans为0，用ll类型存储避免溢出
* 从后往前遍历排序后的数组：
* query(p[i].second -1)：查询已处理元素中，原位置在1~pos-1的数量（即当前元素贡献的逆序对数目），累加到ans
* add(p[i].second)：将当前元素的原位置插入树状数组
五、复杂度分析
时间复杂度
* 排序：O(nlogn)
* 树状数组操作：遍历n次，每次query和add的时间复杂度为O(logn)
* 总时间复杂度：O(nlogn)
* 验证：当n=5×10^5时，log2(5×10^5)≈19，总操作量约9.5×10^6，远小于10^8，完全符合时间要求
空间复杂度
* 使用了两个数组arr和p，空间复杂度均为O(n)
* 总空间复杂度：O(n)
* 验证：5×10^5个int类型元素约占2MB，完全符合空间限制
六、易错点&坑点
1. 数据类型溢出：逆序对数目最大可达n*(n-1)/2≈1.25×10^11，必须用long long存储答案，否则会溢出int的范围（int最大约2×10^9）
2. 输入输出效率：n较大时，必须使用scanf/printf而非cin/cout，否则会超时
3. 排序顺序：必须按数值从小到大排序后从后往前遍历，若顺序搞反会导致统计结果错误；相同数值的元素需按原位置升序排序，避免统计相等元素为逆序对
4. 树状数组下标：树状数组下标从1开始，原位置也从1开始存储，避免lowbit(0)导致的死循环
5. 边界处理：当原位置pos=1时，query(pos-1)=query(0)返回0，正确处理了无前置元素的情况
