POJ 2299 Ultra-QuickSort(树状数组+离散化)

题目大意：

　　　　就是说，给你一个序列，然后让你求出这个序列有多少个逆序对，所谓逆序对就是对于这个序列中的元素有a[i]>a[j] 且i<j存在。

　　其实原题是这样说的，给你一个序列，让你用最少的交换次数使得这个序列变成从小到大的排序.

解题思路：

　　一开始是想到了归并的思路，但是没有能写出来代码.

　　先来来范围吧,序列的长度n<=500000+4.   并且每个a[i]<=999 999 999，对于tree[i]，我们知道这个数组肯定是放不下的，所以

我们要进行离散化的处理，关于离散化的处理，我今天才刚刚看课件学会，，，

　　先来谈谈什么是离散化吧。

　　离散化就是说，我现在有一个数组，这个数组中的某些元素值大的或者小的可怕，但是，我所进行的询问和序列中某个元素的值都是无关的，

那么，我们就可以利用离散化来处理，就是说，对于以前的这个数组，在某种不改变原先序列的大小关系的情况下的映射。

　　

•举个例子： –原数组ax [-1, 120, 13, 45, 12, 12] –排序去重后得到[-1, 12, 13, 45, 120] –映射完后得到新的ax数组 [1,5,3,4,2,2] •一种比较简单的写法： –将所有操作到的数用一个数组存起来，然后排序，去重，该数在数组中的下标就是映射后的新的编号。

　

1 void discrete() 2 { 3 memset(data,0,sizeof(data)); 4 for ( int i = 0;i < n;i++ ) 5 { 6 data[i] = a[i]; 7 } 8 sort(data,data+n); 9 int cc = unique(data,data+n)-data; 10 for ( int i = 0;i < n;i++ ) 11 { 12 a[i] = 1+lower_bound(data,data+cc,a[i])-data; 13 } 14 }

 

现在来讨论下，如何利用BIT来求解逆序数呢？

　　

3. 离散之后，怎么使用离散后的结果数组来进行树状数组操作，计算出逆序数？

    如果数据不是很大， 可以一个个插入到树状数组中，

    每插入一个数， 统计比他小的数的个数，

    对应的逆序为 i- read(a[i]),

    其中 i 为当前已经插入的数的个数，也就是插入的这个数字的下标了.

    read(a[i])为比 a[i] 小的数的个数,

    i- read( a[i] ) 即比 a[i] 大的个数， 即逆序的个数

    但如果数据比较大，就必须采用离散化方法

    假设输入的数组是9 1 0 5 4， 离散后的结果aa[] = {5,2,1,4,3};

在离散结果中间结果的基础上，那么其计算逆序数的过程是这么一个过程。

1，输入5，   调用update(5, 1),把第5位设置为1

1 2 3 4 5

0 0 0 0 1

计算1-5上比5小的数字存在么？ 这里用到了树状数组的read（5） = 1操作，

现在用输入的下标1 - read(5) = 0 就可以得到对于5的逆序数为0。

2. 输入2， 调用update(2, 1),把第2位设置为1

1 2 3 4 5

0 1 0 0 1

计算1-2上比2小的数字存在么？ 这里用到了树状数组的read（2） = 1操作，

现在用输入的下标2 - read(2) = 1 就可以得到对于2的逆序数为1。

3. 输入1， 调用update(1, 1),把第1位设置为1

1 2 3 4 5

1 1 0 0 1

计算1-1上比1小的数字存在么？ 这里用到了树状数组的read（1） = 1操作，

现在用输入的下标 3 - read(1) = 2 就可以得到对于1的逆序数为2。

4. 输入4， 调用update(4, 1),把第5位设置为1

1 2 3 4 5

1 1 0 1 1

计算1-4上比4小的数字存在么？ 这里用到了树状数组的read（4） = 3操作，

现在用输入的下标4 - read(4) = 1 就可以得到对于4的逆序数为1。

5. 输入3， 调用update(3, 1),把第3位设置为1

1 2 3 4 5

1 1 1 1 1

计算1-3上比3小的数字存在么？ 这里用到了树状数组read（3） = 3操作，

现在用输入的下标5 - read(3) = 2 就可以得到对于3的逆序数为2。

6. 0+1+2+1+2 = 6 这就是最后的逆序数

分析一下时间复杂度，首先用到快速排序，时间复杂度为O(NlogN),

后面是循环插入每一个数字，每次插入一个数字，分别调用一次update()和read()

外循环N, update()和read()时间O(logN) => 时间复杂度还是O(NlogN).

最后总的还是O(NlogN).

 

 

代码：

1 # include<iostream> 2 # include<cstdio> 3 # include<algorithm> 4 # include<cstring> 5 6 using namespace std; 7 8 # define MAX 500000+4 9 10 typedef long long LL; 11 12 LL a[MAX]; 13 LL data[MAX]; 14 int tree[MAX]; 15 int n; 16 17 void discrete() 18 { 19 memset(data,0,sizeof(data)); 20 for ( int i = 0;i < n;i++ ) 21 { 22 data[i] = a[i]; 23 } 24 sort(data,data+n); 25 int cc = unique(data,data+n)-data; 26 for ( int i = 0;i < n;i++ ) 27 { 28 a[i] = 1+lower_bound(data,data+cc,a[i])-data; 29 } 30 } 31 32 33 void update ( int pos,int val ) 34 { 35 while ( pos <= n ) 36 { 37 tree[pos]+=val; 38 pos += pos&(-pos); 39 } 40 } 41 42 int read ( int pos ) 43 { 44 int sum = 0; 45 while ( pos>0 ) 46 { 47 sum+=tree[pos]; 48 pos-=pos&(-pos); 49 } 50 return sum; 51 } 52 53 54 int main(void) 55 { 56 while ( cin>>n ) 57 { 58 if ( n==0 ) 59 break; 60 LL ans = 0; 61 for ( int i = 0;i < n;i++ ) 62 { 63 cin>>a[i]; 64 } 65 discrete(); 66 memset(tree,0,sizeof(tree)); 67 for ( int i = 0;i < n;i++ ) 68 { 69 update(a[i],1); 70 ans+=(i+1)-read(a[i]); 71 } 72 cout<<ans<<endl; 73 } 74 75 return 0; 76 }

 

转载于:https://www.cnblogs.com/wikioibai/p/4457176.html

总结

以上是生活随笔为你收集整理的POJ 2299 Ultra-QuickSort(树状数组+离散化)的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。