震惊于没人用逆序对

#include <bits/stdc++.h>
using namespace std;
const int maxn=5e5+10;
int n;
int a[maxn],b[maxn];
long long t[maxn];
int lowbit(int x){
	return x&(-x);
}
void Add(int k,int x){
	while(k<=n){
		t[k]+=x;
		k+=lowbit(k);
	}
}
long long Find(int y){
	long long res=0;
	while(y>0){
		res+=t[y];
		y=y-lowbit(y);
	}
	return res;
}
int main(){
	int TT;
	cin>>TT;
	while(TT--){
		memset(a,0,sizeof(a));
		memset(b,0,sizeof(b));
		memset(t,0,sizeof(t));
		scanf("%d",&n);
		for(int i=1;i<=n;i++){
			scanf("%d",&a[i]);
			b[i]=a[i];
		}
		sort(b+1,b+1+n);
		int len=unique(b+1,b+1+n)-b-1;
		for(int i=1;i<=n;i++){
			a[i]=lower_bound(b+1,b+len+1,a[i])-b;
		}
		long long res=0;
		for(int i=1;i<=n;i++){
			Add(a[i],1);
			res+=Find(n)-Find(a[i]);
		}
		printf("Optimal train swapping takes %lld swaps.\n",res);
	}
	
}