题解：逆序对

题目分析

给定一个长度为 n 的序列，求其中逆序对的数量。逆序对定义为满足 i < j 且 a[i] > a[j] 的数对。

n ≤ 5×10^5，暴力 O(n^2) 会超时，需要使用更高效的算法。
解法：离散化 + 树状数组

核心思路：从右往左遍历数组，对于当前元素 a[i]，统计已经遍历过的元素中有多少个比它小，这些就是与 a[i] 构成的逆序对。
步骤：

1. 离散化：因为 a[i] ≤ 10^9，不能直接用值域开数组，需要将原数组排序去重，映射到 1~m 的范围内。

2. 树状数组：维护每个值出现的次数，支持单点修改和前缀和查询。

3. 从右往左遍历： 查询当前元素离散化后位置 k 的前缀和 sum(k-1)，即比当前元素小的元素个数，累加到答案。

将当前元素的位置 k 加 1，表示该值出现了一次。

复杂度分析

时间复杂度：O(n log n)

空间复杂度：O(n)

#include<cstdio>
#include<algorithm>
using namespace std;
int n,a[500005],b[500005],c[500005];
int lowbit(int x){return x&(-x);}
void add(int x,int y){
    for(int i=x;i<=n;i+=lowbit(i))c[i]+=y;
}
long long sum(int x){
    long long res=0;
    for(int i=x;i>0;i-=lowbit(i))res+=c[i];
    return res;
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        b[i]=a[i];
    }
    sort(b+1,b+n+1);
    int m=unique(b+1,b+n+1)-b-1;
    long long ans=0;
    for(int i=n;i>=1;i--){
        int k=lower_bound(b+1,b+m+1,a[i])-b;
        ans+=sum(k-1);
        add(k,1);
    }
    printf("%lld",ans);
    return 0;
}