coreBugZJ

此 blog 已棄。

歸并樹

記錄歸并排序的中間結(jié)果。

我的代碼：

1 // MergeTree begin
2
3 // T(),  T < T, T = T
4 // ensure 2^NL >  ri
5 // [ le, ri ]
6
7 template<class T, int NL>
8 class MergeTree
9 {
10 public :
11         void init( const T d[], int le, int ri, int dep = 0, int v = 1 ) {
12                 left[ v ]  = le;
13                 right[ v ] = ri;
14                 if ( le == ri ) {
15                         data[ dep ][ le ] = d[ le ];
16                         return;
17                 }
18                 int mid = ( le + ri ) / 2;
19                 init( d, le, mid, dep + 1, v + v );
20                 init( d, mid + 1, ri, dep + 1, v + v + 1 );
21                 int i = le, j = mid + 1, k = le;
22                 while ( ( i <= mid ) && ( j <= ri ) ) {
23                         if ( data[ dep + 1 ][ i ] < data[ dep + 1 ][ j ] ) {
24                                 data[ dep ][ k++ ] = data[ dep + 1 ][ i++ ];
25                         }
26                         else {
27                                 data[ dep ][ k++ ] = data[ dep + 1 ][ j++ ];
28                         }
29                 }
30                 while ( i <= mid ) {
31                         data[ dep ][ k++ ] = data[ dep + 1 ][ i++ ];
32                 }
33                 while ( j <= ri ) {
34                         data[ dep ][ k++ ] = data[ dep + 1 ][ j++ ];
35                 }
36         }
37         int getCountBelow( int le, int ri, const T & da, int dep = 0, int v = 1 ) {
38                 if ( ( ri < left[ v ] ) || ( right[ v ] < le ) ) {
39                         return 0;
40                 }
41                 if ( ( le <= left[ v ] ) && ( right[ v ] <= ri ) ) {
42                         int low = left[ v ], high = right[ v ], mid, ans = left[ v ] - 1;
43                         while ( low <= high ) {
44                                 mid = ( low + high ) >> 1;
45                                 if ( data[ dep ][ mid ] < da ) {
46                                         low = mid + 1;
47                                         if ( ans < mid ) {
48                                                 ans = mid;
49                                         }
50                                 }
51                                 else {
52                                         high = mid - 1;
53                                 }
54                         }
55                         return ans - left[ v ] + 1;
56                 }
57                 return getCountBelow( le, ri, da, dep + 1, v + v ) +
58                        getCountBelow( le, ri, da, dep + 1, v + v + 1 );
59         }
60         // k = 1, 2,

, ri - le + 1, le <= ri
61         T getKth( int le, int ri, int k ) {
62                 int low = left[ 1 ], high = right[ 1 ], mid, rk, ans = left[ 1 ];
63                 while ( low <= high ) {
64                         mid = ( low + high ) >> 1;
65                         rk = getCountBelow( le, ri, data[ 0 ][ mid ] ) + 1;
66                         if ( rk <= k ) {
67                                 low = mid + 1;
68                                 if ( mid > ans ) {
69                                         ans = mid;
70                                 }
71                         }
72                         else {
73                                 high = mid - 1;
74                         }
75                 }
76                 return data[ 0 ][ ans ];
77         }
78 private :
79         T  data[ NL ][ 1 << NL ];
80         int left[ 4 << NL ], right[ 4 << NL ];
81 };
82
83 // MergeTree end
84

posted on 2011-03-20 19:44 coreBugZJ 閱讀(1804) 評(píng)論(0) 編輯收藏引用所屬分類: DataStructure

只有注冊用戶登錄后才能發(fā)表評(píng)論。
【推薦】100%開源！大型工業(yè)跨平臺(tái)軟件C++源碼提供，建模，組態(tài)！

相關(guān)文章: POJ 3277 City Horizon POJ 2528 Mayor's posters EOJ 2458 Frequent values EOJ 2525 Light Switching EOJ 1010 智能T9英文輸入法字典樹歸并樹 Treap AVL 樹

網(wǎng)站導(dǎo)航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理

coreBugZJ

My Links

Blog Stats

常用鏈接

留言簿(10)

隨筆分類(458)

隨筆檔案(268)

相冊

ACM

AI

LaTeX

安全

編程語言

好有道理

技術(shù)

開源

科學(xué)

數(shù)學(xué)

圖形圖像

文化

問題（練習(xí)＆有趣）

資源

最新隨筆

搜索

最新評(píng)論

閱讀排行榜

評(píng)論排行榜

歸并樹