P1908 逆序对

P1908 逆序对 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

树状数组可以干这个事情

树桩数组维护一个下标啦

然后离散化一下，sort，unique，二分确定每一个数在新序列的下标

也就是第i个数大小的排名。

然后算一下有多少个数，拍在他前面且大小排名在它之前。

#include<iostream>
#include<cstdio>
#include<algorithm>
#define int long long 
using namespace std;
int n;
int a[5000001];
int b[5000001];
int id[5000001];
int tr[5000001];
inline int lowbit(int x){
	return x&(-x);
}
void add(int x){
	for(int i=x;i<=n;i+=lowbit(i)){
		tr[i]++;
	}
}
int query(int x){
	int res=0;
	for(int i=x;i>0;i-=lowbit(i)){
		res+=tr[i];
	}
	return res;

}

signed main(){
	scanf("%d",&n);
	for(int i=1;i<=n;++i){
		scanf("%d",&a[i]);
		b[i]=a[i];
	}
	sort(a+1,a+n+1);
	int nn=unique(a+1,a+n+1)-a-1;
	for(int i=1;i<=n;++i){
		id[i]=upper_bound(a+1,a+n+1,b[i])-a-1;
	}
	int ans=0;
	for(int i=1;i<=n;++i){
		ans+=i-1-query(id[i]);
		add(id[i]);
	}
	cout<<ans;
	return 0;
}