树状数组 _ 求逆序数

5
9
1
0
5
4
3
1
2
3
0

6
0

import java.util.Arrays;
import java.util.Scanner;

/**
 * 树状数组
 * @author Administrator
 *
 */

class Node implements Comparable<Node>{
    public int index;
    public int value;
    
    public Node(int index,int value){
        this.index = index;
        this.value = value;
    }
    
    @Override
    public int compareTo(Node n) {
        return this.value-n.value;
    }
    
}
public class TreeArrayDemo {
    
    private static int [] c ;
    private static int [] array = new int [500010];
    private static int maxn;
    private static Node [] nodes ;
    
    public static int lowbit(int x){
        return x&(-x);
    }

    public static int getSum(int x)
    {
        int sum  = 0 ;
        for(int i = x;i>0;i-=lowbit(i)){
            sum+=c[i];
        }
        return sum;
    }
    
    public static void update(int x,int val)
    {
        for(int i = x;i<=maxn;i+=lowbit(i)){
            c[i]+=val;
        }

        
    }
    
    
    
    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        while (cin.hasNext()) {
            maxn = cin.nextInt();
            
            if(maxn == 0)
            {
                break;
            }
            nodes = new Node [500010];
            c = new int [500010];
            
            
            for(int i = 1;i<=maxn;i++){
                int index = i;
                int val = cin.nextInt();
                Node node = new Node(index, val);
                nodes[i] = node;
            }
            //给节点进行排序
            Arrays.sort(nodes, 1,maxn+1);
            
            //对数据进行离散化
            for(int i = 1;i<=maxn;i++){
                array[nodes[i].index] = i;
            }
            
            for(int i = 1;i<=maxn;i++){
                System.out.println(array[i]);
            }
            
            long answer = 0;
            for(int i = 1;i<=maxn;i++)
            {
                update(array[i], 1);
                int n = getSum(array[i]);
                answer+=i-n;
            }
            
            System.out.println(answer);
        }
        
        
    }
    
    
}