逆序对

zyc123 · 2019-11-14 19:43:52 · 个人记录

就是树状数组的应用，顺便还有离散化代码

#include <iostream>
#include <algorithm>
#include <cstdio>
#define int long long
using namespace std;
struct node
{
    int id; int v;
};
int n,cnt,ans;
node a[500010];
int c[500010],t[500010];
bool cmp(node x,node y)
{
    return x.v<y.v;
}
int lowbit(int x)
{
    return x&(-x);
}
void add(int x,int y)
{
    while(x<=n)
    {
        t[x]+=y;
        x+=lowbit(x);
    }
}
int ask(int x)
{
    int ans=0;
    while(x>0)
    {
        ans+=t[x];
        x-=lowbit(x);
    }
    return ans;
}
signed main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        scanf("%lld",&a[i].v);
        a[i].id=i;
    }
    sort(a+1,a+1+n,cmp);
    for(int i=1;i<=n;i++)
    {
        if(a[i].v!=a[i-1].v) cnt++;
        c[a[i].id]=cnt;
    }
    for(int i=1;i<=n;i++)
    {
        int what=c[i];
        add(what,1);
        ans+=i-ask(what);
    }
    cout<<ans;
}