In this problem, you have to analyze a particular sorting algorithm. The algorithm processes a sequence of n distinct integers by swapping two adjacent sequence elements until the sequence is sorted in ascending order. For the input sequence
9 1 0 5 4 ,
Ultra-QuickSort produces the output
0 1 4 5 9 .
Your task is to determine how many swap operations Ultra-QuickSort needs to perform in order to sort a given input sequence.
Input
The input contains several test cases. Every test case begins with a line that contains a single integer n < 500,000 -- the length of the input sequence. Each of the the following n lines contains a single integer 0 ≤ a[i] ≤ 999,999,999, the i-th input sequence element. Input is terminated by a sequence of length n = 0. This sequence must not be processed.
Output
For every input sequence, your program prints a single line containing an integer number op, the minimum number of swap operations necessary to sort the given input sequence.
Sample Input
5 9 1 0 5 4 3 1 2 3 0Sample Output
6 0题意： 给你n个数，每次只能交换相邻的两个数，求最小交换次数
思路： 首先这是一个求逆序对的问题，其次数据很大且数据的个数小需要离散化处理
0 ≤ a[i] ≤ 999,999,999，很明显数据很大，如果一个数为0，另一个数为999999999，只有这两个数，不离散化需要建一个很大的树，而实际情况只需要建一个很小的树，因为只有两个数
什么时候离散化： 数据的范围非常大或者其中含有负数，但数据本身的个数并不是很多（远小于数据范围）。在这种情况下，如果每个数据元素的具体值并不重要，重要的是他们之间的大小关系的话，我们可以先对这些数据进行离散化，使数据中的最大值尽可能小且保证所有数据都是正数。
离散化过程：
val: 9 1 0 5 4
index： 1 2 3 4 5
sort:
val: 0 1 4 5 9
index: 3 2 5 4 1
arr[index]: 1 2 3 4 5
import java.util.Arrays; import java.util.Comparator; import java.util.Scanner; class Num{ int val; int index; } class cmp implements Comparator<Num>{ @Override public int compare(Num o1, Num o2) { if(o1.val>o2.val) return 1; else if(o1.val==o2.val) return 0; else return -1; } } public class Main { static int n; static final int max=500005; static long tree[]=new long[max<<2]; static int arr[]=new int[max]; public static void update(int node,int l,int r,int a,int b){ if(l==a&&r==b){ tree[node]+=1; return ; } int mid=(l+r)/2; if(a<=mid) update(node<<1,l,mid,a,b); else if(b>mid) update(node<<1|1,mid+1,r,a,b); tree[node]=tree[node<<1]+tree[node<<1|1]; } public static long query(int node,int l,int r,int a,int b){ if(l>=a&&r<=b){ return tree[node]; } int mid=(l+r)/2; if(b<=mid) return query(node<<1,l,mid,a,b); else if(a>mid) return query(node<<1|1,mid+1,r,a,b); else return query(node<<1,l,mid,a,b)+query(node<<1|1,mid+1,r,a,b); } public static void main(String[] args) { Scanner scan=new Scanner(System.in); while(scan.hasNext()){ n=scan.nextInt(); if(n==0) break; Arrays.fill(tree, 0); Num num[]=new Num[n+1]; int max=0; for(int i=1;i<=n;i++){ num[i]=new Num(); num[i].val=scan.nextInt(); num[i].index=i; } //离散化 Arrays.sort(num,1,n+1,new cmp());//sort不包括右边界 for(int i=1;i<=n;i++) arr[num[i].index]=i; long sum=0;//逆序对数量很大，用long for(int i=1;i<=n;i++){ int a=arr[i]; update(1,1,n,a,a); sum+=(i-query(1,1,n,1,a)); } System.out.println(sum); } } }
