求逆序对个数(树状数组)
程序员文章站
2022-05-10 15:13:19
...
#include<iostream>
#include<algorithm>
#define ll long long
using namespace std;
const int maxn=100010;
struct node{
int w;
int p;
}a[maxn];
int n;
int bit[maxn];
int cmp(node a,node b){
if(a.w==b.w) return a.p<b.p;
else return a.w<b.w;
}
void update(int i,int x){
while (i<=n){
bit[i]+=x;
i+=i&-i;
}
}
ll sum(int i){
ll ans=0;
while (i){
ans+=bit[i];
i-=i&-i;
}
return ans;
}
int book[maxn];
int main(){
cin>>n;
for (int i=1;i<=n;i++){
cin>>a[i].w;
a[i].p=i;
}
sort(a+1,a+1+n,cmp);
for (int i=1;i<=n;i++)
book[a[i].p]=i;
long long ans=0;
for (int i=1;i<=n;i++){
update(book[i],1);
ans+=i-sum(book[i]);
}
cout<<ans;
}
上一篇: $('')是什么意思、解决思路
下一篇: php处理json时中文问题的解决方法