逆序对即满足 且 的 的对数。
我们可以将 倒序插入数据结构，这样即满足了 的限制条件。然后查询数据结构中小于 的数的个数，累加到答案中即可。这里使用树状数组。
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=32770;
int n,a[N];
struct Fenwick{
int tr[N];
inline int lowbit(int x){return x&-x;}
void add(int x,int k){
while(x<N)tr[x]+=k,x+=lowbit(x);
}
int query(int x){
int res=0;
while(x>0)res+=tr[x],x-=lowbit(x);
return res;
}
}bit;
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin>>n;int ans=0;
for(int i=1;i<=n;i++)cin>>a[i];
for(int i=n;i>=1;i--){
bit.add(a[i],1);
ans+=bit.query(a[i]-1);
}cout<<ans;
}
暂无评论