題目大意：

　　　　就是說(shuō)，給你一個(gè)序列，然后讓你求出這個(gè)序列有多少個(gè)逆序?qū)?#xff0c;所謂逆序?qū)褪菍?duì)于這個(gè)序列中的元素有a[i]>a[j] 且i<j存在。

　　其實(shí)原題是這樣說(shuō)的，給你一個(gè)序列，讓你用最少的交換次數(shù)使得這個(gè)序列變成從小到大的排序.

解題思路：

　　一開(kāi)始是想到了歸并的思路，但是沒(méi)有能寫(xiě)出來(lái)代碼.

　　先來(lái)來(lái)范圍吧,序列的長(zhǎng)度n<=500000+4. ? 并且每個(gè)a[i]<=999 999 999，對(duì)于tree[i]，我們知道這個(gè)數(shù)組肯定是放不下的，所以

我們要進(jìn)行離散化的處理，關(guān)于離散化的處理，我今天才剛剛看課件學(xué)會(huì)，，，

　　先來(lái)談?wù)勈裁词请x散化吧。

　　離散化就是說(shuō)，我現(xiàn)在有一個(gè)數(shù)組，這個(gè)數(shù)組中的某些元素值大的或者小的可怕，但是，我所進(jìn)行的詢問(wèn)和序列中某個(gè)元素的值都是無(wú)關(guān)的，

那么，我們就可以利用離散化來(lái)處理，就是說(shuō)，對(duì)于以前的這個(gè)數(shù)組，在某種不改變?cè)刃蛄械拇笮￡P(guān)系的情況下的映射。

　　

?舉個(gè)例子： –原數(shù)組ax [-1, 120, 13, 45, 12, 12] –排序去重后得到[-1, 12, 13, 45, 120] –映射完后得到新的ax數(shù)組 [1,5,3,4,2,2] ?一種比較簡(jiǎn)單的寫(xiě)法： –將所有操作到的數(shù)用一個(gè)數(shù)組存起來(lái)，然后排序，去重，該數(shù)在數(shù)組中的下標(biāo)就是映射后的新的編號(hào)。

　

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 }

?

現(xiàn)在來(lái)討論下，如何利用BIT來(lái)求解逆序數(shù)呢？

　　

3. 離散之后，怎么使用離散后的結(jié)果數(shù)組來(lái)進(jìn)行樹(shù)狀數(shù)組操作，計(jì)算出逆序數(shù)？

??? 如果數(shù)據(jù)不是很大， 可以一個(gè)個(gè)插入到樹(shù)狀數(shù)組中，

??? 每插入一個(gè)數(shù)， 統(tǒng)計(jì)比他小的數(shù)的個(gè)數(shù)，

??? 對(duì)應(yīng)的逆序?yàn)?i- read(a[i]),

??? 其中 i 為當(dāng)前已經(jīng)插入的數(shù)的個(gè)數(shù)，也就是插入的這個(gè)數(shù)字的下標(biāo)了.

??? read(a[i])為比 a[i] 小的數(shù)的個(gè)數(shù),

??? i- read( a[i] ) 即比 a[i] 大的個(gè)數(shù)， 即逆序的個(gè)數(shù)

??? 但如果數(shù)據(jù)比較大，就必須采用離散化方法

??? 假設(shè)輸入的數(shù)組是9 1 0 5 4， 離散后的結(jié)果aa[] = {5,2,1,4,3};

在離散結(jié)果中間結(jié)果的基礎(chǔ)上，那么其計(jì)算逆序數(shù)的過(guò)程是這么一個(gè)過(guò)程。

1，輸入5，?? 調(diào)用update(5, 1),把第5位設(shè)置為1

1 2 3 4 5

0 0 0 0 1

計(jì)算1-5上比5小的數(shù)字存在么？ 這里用到了樹(shù)狀數(shù)組的read（5） = 1操作，

現(xiàn)在用輸入的下標(biāo)1 - read(5) = 0 就可以得到對(duì)于5的逆序數(shù)為0。

2. 輸入2， 調(diào)用update(2, 1),把第2位設(shè)置為1

1 2 3 4 5

0 1 0 0 1

計(jì)算1-2上比2小的數(shù)字存在么？ 這里用到了樹(shù)狀數(shù)組的read（2） = 1操作，

現(xiàn)在用輸入的下標(biāo)2 - read(2) = 1 就可以得到對(duì)于2的逆序數(shù)為1。

3. 輸入1， 調(diào)用update(1, 1),把第1位設(shè)置為1

1 2 3 4 5

1 1 0 0 1

計(jì)算1-1上比1小的數(shù)字存在么？ 這里用到了樹(shù)狀數(shù)組的read（1） = 1操作，

現(xiàn)在用輸入的下標(biāo) 3 - read(1) = 2 就可以得到對(duì)于1的逆序數(shù)為2。

4. 輸入4， 調(diào)用update(4, 1),把第5位設(shè)置為1

1 2 3 4 5

1 1 0 1 1

計(jì)算1-4上比4小的數(shù)字存在么？ 這里用到了樹(shù)狀數(shù)組的read（4） = 3操作，

現(xiàn)在用輸入的下標(biāo)4 - read(4) = 1 就可以得到對(duì)于4的逆序數(shù)為1。

5. 輸入3， 調(diào)用update(3, 1),把第3位設(shè)置為1

1 2 3 4 5

1 1 1 1 1

計(jì)算1-3上比3小的數(shù)字存在么？ 這里用到了樹(shù)狀數(shù)組read（3） = 3操作，

現(xiàn)在用輸入的下標(biāo)5 - read(3) = 2 就可以得到對(duì)于3的逆序數(shù)為2。

6. 0+1+2+1+2 = 6 這就是最后的逆序數(shù)

分析一下時(shí)間復(fù)雜度，首先用到快速排序，時(shí)間復(fù)雜度為O(NlogN),

后面是循環(huán)插入每一個(gè)數(shù)字，每次插入一個(gè)數(shù)字，分別調(diào)用一次update()和read()

外循環(huán)N, update()和read()時(shí)間O(logN) => 時(shí)間復(fù)雜度還是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 }

?

轉(zhuǎn)載于:https://www.cnblogs.com/wikioibai/p/4457176.html

總結(jié)

以上是生活随笔為你收集整理的POJ 2299 Ultra-QuickSort(树状数组+离散化)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。