题意:
输入一个整数n。
接下来输入一行n个整数 。
1<= <= n ,且每个数字只会出现一次
题解:
按每个数字的大小存入树状数组
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=10000;
int arr[N];
ll a[N];
int n;ll query(int x){ll s=0;for(;x;x-=x&(-x)){s+=a[x];}return s;
}void modify(int p,ll x){for(;p<=n;p+=p&(-p)){a[p]+=x;}
}int main(){scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d",arr+i);//让大于arr[i]的元素在数组数组中排在它的前面方便使用前n项和arr[i]=n+1-arr[i];}ll ans=0;for(int i=1;i<=n;i++){//每一次有多少个大于它的值就会新增多少个逆序对ans+=query(arr[i]);//然后统计完该数的逆序对后,再将该数放入到树状数组中modify(arr[i],1);}printf("%lld",ans);return 0;
}