题目在这里 http://lx.lanqiao.cn/problem.page?gpid=T123
思路是统计每个位置的逆序数。如果是统计所有的逆序数的话，经典的nlogn复杂度的有两种方式，一个是分治，过程和归并排序一样，另一种是使用树状数组。但这里要求的是每个位置的逆序数，如果用归并，每个元素位置可能会变动，处理的比较麻烦点，所以使用树状数组。
从后往前走的话，考虑a[i]，先计算a[i+1]~a[n]在树状数组中，值在1~a[i]-1的元素个数， sum(a[i]-1)，所得到的值就是a[i]的逆序数的一部分，即小于a[i]，且在a[i]后面的元素的个数。计算出来后，再将a[i]加入树状数组中。
对于每个位置的逆序数，我们显然还缺少另外一部分，即大于a[i]，且在a[i]前面的元素的个数。对上面的步骤执行相反的过程即可。注意，这里可以计算的是1~a[i]的个数，逆序数显然是i-1-sum(a[i])。
交了一发，超时，还有错解的。错解是因为爆了int了。改了一下，还是超时。一开始以为是Java效率太低的问题，找了下输入挂，时间是短了点，但还是超。后面发现，输入数据可以包含0。输入的时候，直接都++，搞定。去了输入挂，也可以过，只不过在900+ms，一不小心就超时了。
所以呢，要多从自己找原因，自己代码写残了，该超时还是得超时的。
附上代码。
import java.util.Arrays; import java.util.Scanner; public class Main { static int c[]; static int n; static int lowbit(int x){ return x&-x; } static void add(int x){ while(x<c.length){ c[x] ++; x += lowbit(x); } } static long sum(int x){ long ret = 0; while(x>0){ ret += c[x]; x -= lowbit(x); } return ret; } static void out(){ for(int j=0; j<=5; j++){ System.out.print(c[j] + " "); } System.out.println(); } static int cnt[]; public static void main(String[] args) { c = new int[1000000+1]; Scanner cin = new Scanner(System.in); n = cin.nextInt(); int a[] = new int[n+1]; for(int i=1; i<=n; i++){ a[i] = cin.nextInt(); a[i]++; } cnt = new int[n+1]; Arrays.fill(cnt, 0); Arrays.fill(c, 0); for(int i=n; i>0; i--){ cnt[i] += sum(a[i]-1); add(a[i]); } Arrays.fill(c, 0); for(int i=1; i<=n; i++){ cnt[i] += i - 1 - sum(a[i]); add(a[i]); } long ans = 0; for(int i=1; i<=n; i++){ // System.out.print(cnt[i] + " "); ans +=1l*(cnt[i]+1)*cnt[i]/2; } System.out.println(ans); } }