hiho1524
树状数组求逆序对
import java.util.Scanner;
public class Main {
public static final int N=100050;
public static int n,x;
public static long ans;
public static int[] c=new int[N];
public static void main(String[] args) {
Scanner cin=new Scanner(System.in);
n=cin.nextInt();
for(int i=1;i<=n;i++){
x=cin.nextInt();
add(x,1);
ans+=(i-sum(x));
}
System.out.println(ans);
}
public static int lowbit(int x){
return x&(-x);
}
public static void add(int x,int d){
while(x<=n){
c[x]+=d;
x+=lowbit(x);
}
}
public static int sum(int x){
int res=0;
while(x>0){
res+=c[x];
x-=lowbit(x);
}
return res;
}
}