看不懂其他人的,只能自己写了
使用pair双关键字降序排序,first是值,second是下标。
那么遍历排序后的数组a,是从大到小遍历的,每次遍历过一个数,就将它的下标i加入树状数组中(由于计算的是个数,那么权值是1),那么遍历到某一个数时,比这个数大的数一定已经在树状数组中了,query(i-1)计算的就是1~i-1中已经出现了多少个数(这些数一定满足下标比i小,值比a[i]大)
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=1e5+10;
int t[N],n;
pair<int,int> a[N];
int lowbit(int x)
{
return x&-x;
}
void add(int k,int x)
{
for(int i=k;i<=n;i+=lowbit(i))t[i]+=x;
}
ll query(int k)
{
ll ans=0;
for(int i=k;i;i-=lowbit(i))ans+=t[i];
return ans;
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i].first);
a[i].second=i;
}
sort(a+1,a+n+1);
ll ans=0;
for(int i=n;i>=1;i--)
{
ans+=query(a[i].second-1);
add(a[i].second,1);
}
printf("%lld",ans);
return 0;
}