题解 | #逆序数#

• 题目考点：归并排序、二维偏序都可以写，也都是模板题

• 题目大意：给定一个数组，对于数组中的每一个数ai,如果前面有一个数aj大于ai,那么(aj,ai)组成一组逆序对,数组中逆序数的个数为数组的逆序数，求逆序数的数量。

• 思考：既然有不少同学写了归并排序，我就写一写二维偏序吧！思路很简单，我们把数字一个一个放入另一个数组，对于当前数字，我们只用看已经放入的数字中有多少是大于当前数字的就好。放入和统计个数交给树状数组去维护即可。

• 插一句：逆序数也是二维偏序的经典问题，即有类似 (ai,aj) 和 (bi,bj), ai < bi , aj < bj的限制。

代码:

#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

const int N = 100010;
typedef long long LL;

int tr[N], n;
LL ans;

int lowbit(int x)         // 树状数组三大件:lowbit、add、que
{
    return x & -x;
}

void add(int t, int x)    // add是从前往后
{
    for(int i = t; i <= N; i += lowbit(i)) tr[i] += x;
}

LL que(int x)            // que是从后往前
{
    LL cnt = 0;
    for(int i = x; i ; i -= lowbit(i)) cnt += tr[i];
    return cnt;
}

int main()
{
    scanf("%d", &n);
    
    for(int i = 1; i <= n; i++)
    {
        int x; scanf("%d", &x);
        ans += que(N-10) - que(x-1);  // 用树状数组求前缀和算出当前数字后面有几个数字
        //cout << x << ' ' << que(N) << ' ' << que(x-1) << '\n'; 
        add(x, 1);                   // 当前数字放入树状数组
    }
    
    printf("%lld", ans);
    return 0;
}