题目描述

（2020年8月2日所写，现在数据范围已提升，本解析代码只供各位参考学习）
树状数组求逆序对的数量：

给定一个长度为n的整数数列，请你计算数列中的逆序对的数量。
逆序对的定义如下：对于数列的第 i 个和第 j 个元素，如果满足 i < j 且 a[i] > a[j]，则其为一个逆序对；否则不是。

输入样例

6
2 3 4 5 6 1

输出样例

5

算法

树状数组

const int N = 1060000
因为这个树状数组的下标是数的范围，不是题中的n，数的个数的范围。
然后利用树状数组的区间查询，去算有多少个数的位置在这个数之前，并且大于他的。

#include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;

typedef long long LL;

const int N = 1060000;

int n,m;
int w[N],tr[N];

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

void add(int x,int v){
    for(int i=x;i<=N;i+=lowbit(i)) tr[i]+=v;
}

int query(int x){
    int sum=0;
    for(int i=x;i;i-=lowbit(i)) sum+=tr[i];
    return sum;
}

int main(){
    scanf("%d",&n);

    for(int i=0;i<n;i++) scanf("%d",&w[i]);

    LL sum=0;
    for(int i=0;i<n;i++){
        sum+=(query(N)-query(w[i]));
        add(w[i],1);
    }

    printf("%lld",sum);

    return 0;
}