【ybt】【数据结构 树状数组 课过 例2】逆序对

本文主要是介绍【ybt】【数据结构 树状数组 课过 例2】逆序对，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

逆序对

题目链接：YbtOJ/Luogu

---

解题思路

我们可以进行离散化，然后用树状数组维护下标，每次在树状数组中找下标比当前小的就可以了。

code

#include<algorithm>
#include<iostream>
#include<cstdio>
#define lb(x) (x&(-x))
#define int long long
using namespace std;int n,ans;
int c[5000010];struct abc{int a,b;
}a[500010];bool cmp(abc a,abc b)
{if(a.a!=b.a)return a.a>b.a;return a.b>b.b;
}void in(int x)
{for(;x<=n;x+=lb(x))c[x]++;
}int fd(int x)
{int s=0;for(;x;x-=lb(x))s+=c[x];return s;
}signed main()
{cin>>n;for(int i=1;i<=n;i++){scanf("%lld",&a[i].a);a[i].b=i;}sort(a+1,a+n+1,cmp);for(int i=1;i<=n;i++){in(a[i].b);ans+=fd(a[i].b-1);}cout<<ans<<endl;
}

这篇关于【ybt】【数据结构 树状数组 课过 例2】逆序对的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---