POJ 2299 Ultra-QuickSort （树状数组+离散化）

Ultra-QuickSort Time Limit: 7000MS Memory Limit: 65536KTotal Submissions: 55640 Accepted: 20534

Description

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 0

Sample Output

6 0

Source

Waterloo local 2005.02.05 题意：给出一个长度为n的数列，你每一次可以随意交换其中两个数字的位置。问你至少交换几次，才能使得这个数列是个单调递增数列。 思路：虽然能想到是求每个数前面有几个比它大的数，然后相加，但是n比较大，a[i]也很大，这就比较麻烦了。离散化+树状数组。 离散化：

有些数据本身很大， 自身无法作为数组的下标保存对应的属性。

如果这时只是需要这堆数据的相对属性， 那么可以对其进行离散化处理！ 离散化：当数据只与它们之间的相对大小有关，而与具体是多少无关时，可以进行离散化。 设有4个数： 1234567、123456789、12345678、123456 排序：123456<1234567<12345678<123456789            =>     1     <        2       <        3       <        4 那么这4个数可以表示成：2、4、3、1 使用STL算法离散化： 思路：先排序，再删除重复元素，然后就是索引元素离散化后对应的值。 假定待离散化的序列为a[n]，b[n]是序列a[n]的一个副本，则对应以上三步为： sort(sub_a,sub_a+n); int size=unique(sub_a,sub_a+n)-sub_a;//size为离散化后元素个数 for(i=0;i<n;i++) a[i]=lower_bound(sub_a,sub_a+size,a[i])-sub_a + 1;//k为b[i]经离散化后对应的值 对于第3步，若离散化后序列为0, 1, 2, ..., size - 1则用lower_bound，从1, 2, 3, ..., size则用upper_bound，其中lower_bound返回第1个不小于b[i]的值的指针，而upper_bound返回第1个大于b[i]的值的指针，当然在这个题中也可以用lower_bound然后再加1得到与upper_bound相同结果，两者都是针对以排好序列。使用STL离散化大大减少了代码量且结构相当清晰。

#include<stdio.h> #include<string.h> #include<algorithm> #define MAX 500010 using namespace std; int b[MAX]; int c[MAX]; struct node { int val,index; }t[MAX]; bool cmp(node a,node b) { return a.val<b.val; } int n; void add(int x,int val) { while(x<=n) { b[x]+=val; x+=(x&(-x)); } } int sum(int x) { int ans=0; while(x>0) { ans+=b[x]; x-=(x&(-x)); } return ans; } int main() { int i; while(scanf("%d",&n),n) { for(i=1;i<=n;i++) { scanf("%d",&t[i].val); t[i].index=i; } memset(b,0,sizeof(b)); memset(c,0,sizeof(c)); sort(t+1,t+n+1,cmp); c[t[1].index]=1; for(i=2;i<=n;i++) { if(t[i].val!=t[i-1].val) c[t[i].index]=i; else c[t[i].index]=c[t[i-1].index]; } __int64 ans=0; for(i=1;i<=n;i++) { add(c[i],1); ans+=sum(n)-sum(c[i]); } printf("%I64d\n",ans); } return 0; }