逆序对

一、题目简述

核心要求

给定一个长度为n的正整数序列，统计其中逆序对的数目。逆序对的定义为：序列中满足 $a_i > a_j$ 且 $i < j$ 的有序对 (i,j)。

数据范围

• 序列长度：1 ≤ n ≤ 5×10^5
• 元素大小：每个数字不超过 10^9

二、样例解析

样例输入

6
5 4 2 6 3 1

样例输出

11

推导过程

我们可以逐个统计每个元素作为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的组合，判断 $a_i > a_j$并计数。

• 时间复杂度：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. 累加结果：将所有元素的贡献累加得到总逆序对数目

四、代码详解

int lowbit(int x) {
    return x & -x;
}

• 作用：返回x的最低位1对应的数值，是树状数组更新和查询的核心，用于快速定位树状数组的节点

void add(int x) {
    for (int i = x; i <= n; i += lowbit(i))
        arr[i]++;
}

• 作用：单点更新，将树状数组中位置x的元素计数加1
• 逻辑：通过lowbit快速跳转到父节点，更新所有相关节点

ll query(int x) {
    ll res = 0;
    for (int i = x; i > 0; i -= lowbit(i))
        res += arr[i];
    return res;
}

• 作用：查询前缀和，返回1~x位置的元素总数
• 逻辑：通过lowbit快速跳转到子节点，累加所有相关节点的数值

    sort(p + 1, p + n + 1);

• 对p数组排序，默认按pair的first（数值）升序、second（原位置）升序排列，确保数值小的在前，数值相同的原位置小的在前

    ll ans = 0;
    for (int i = n; i >= 1; i--) {
        ans += query(p[i].second - 1);
        add(p[i].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，正确处理了无前置元素的情况