coreBugZJ

此 blog 已棄。

歸并樹

記錄歸并排序的中間結果。

我的代碼：

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 閱讀(1821) 評論(0) 編輯收藏引用所屬分類: DataStructure

只有注冊用戶登錄后才能發表評論。


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

網站導航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

coreBugZJ

My Links

Blog Stats

常用鏈接

留言簿(10)

隨筆分類(458)

隨筆檔案(268)

相冊

ACM

AI

LaTeX

安全

編程語言

好有道理

技術

開源

科學

數學

圖形圖像

文化

問題（練習＆有趣）

資源

最新隨筆

搜索

最新評論

閱讀排行榜

評論排行榜

歸并樹