题解 P1908 【逆序对】

Drug__Lover · 2017-10-24 09:58:26 · 题解

离散化一下

按价值从大到小排序

排完序之后用树状数组维护

每次把这个数的位置加入到树状数组中

因为是排完序之后，所以之前加入的一定比后加入的大

然后在查询当前这个数前面位置的数（是前面位置的数，要当前这个数减1）

就是逆序对的个数了

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define maxn 50000
using namespace std;
struct node
{
    int val,num;
}a[maxn];
int n;
int c[maxn];
int add(int x,int k)
{
    for(int i=x;i<=n;i+=i&(-i)) c[i]+=k;
}
int query(int x)
{
    int sum=0;
    for(int i=x;i>0;i-=i&(-i)) sum+=c[i];
    return sum;
}
int cmp(node x,node y)
{
    return x.val>y.val;
}
int ans;
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++) scanf("%d",&a[i].val),a[i].num=i;
    sort(a+1,a+n+1,cmp);
    for(int i=1;i<=n;i++)
    {
        add(a[i].num,1);
        ans+=query(a[i].num-1);
    }
    cout<<ans<<endl;
}