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

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

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品
  • <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            国产日韩精品在线| 亚洲在线一区二区三区| 亚洲大胆av| 欧美成人中文| 亚洲精选国产| 亚洲欧美日韩综合国产aⅴ| 国产精品久久九九| 欧美一区激情| 欧美成人精品1314www| 日韩视频免费在线| 国产精品夜夜夜| 久久一区免费| 一本一本久久| 久久综合一区二区三区| 日韩小视频在线观看| 国产精品成人在线| 久久9热精品视频| 亚洲人午夜精品| 亚洲欧美日韩天堂| 一区二区在线视频播放| 欧美日韩免费观看一区三区 | 午夜精品一区二区三区在线| 久久先锋影音| 宅男噜噜噜66国产日韩在线观看| 国产日韩欧美在线一区| 欧美激情在线有限公司| 性久久久久久| 99国内精品久久| 麻豆免费精品视频| 亚洲一区二区在线观看视频| 精品动漫一区| 国产精品日韩二区| 欧美国产大片| 久久精品国产精品亚洲综合| 一本色道久久综合亚洲二区三区 | 欧美激情视频网站| 午夜免费在线观看精品视频| 91久久综合| 美女任你摸久久| 久久国产黑丝| 亚洲一区精品视频| 亚洲人人精品| 亚洲第一毛片| 国内精品免费在线观看| 国产精品xnxxcom| 欧美激情在线| 免费观看日韩av| 久久久久久久久久码影片| 亚洲男人的天堂在线观看 | 日韩一级精品| 亚洲第一黄网| 欧美成人精品在线视频| 久久精品理论片| 欧美一区二区三区另类| 亚洲一区二区成人在线观看| 亚洲精品国产精品乱码不99| 精品69视频一区二区三区| 国产精品永久免费观看| 国产精品第一区| 欧美日韩视频在线观看一区二区三区 | 老妇喷水一区二区三区| 欧美主播一区二区三区美女 久久精品人 | 美女精品网站| 老司机精品导航| 久久女同精品一区二区| 久久久久网址| 久久久精品国产免大香伊| 久久黄色网页| 久久久精品网| 久久久精彩视频| 久久夜色撩人精品| 久久久久一区二区| 久久视频这里只有精品| 久久深夜福利| 欧美成人午夜剧场免费观看| 蜜臀av性久久久久蜜臀aⅴ| 男女视频一区二区| 欧美高清视频免费观看| 亚洲国产精品综合| 亚洲欧洲日本国产| 夜夜嗨av一区二区三区网页| 亚洲视频一二区| 亚洲欧美激情诱惑| 性做久久久久久免费观看欧美| 小黄鸭精品密入口导航| 欧美影院成人| 麻豆精品在线播放| 欧美成人高清| 国产精品v欧美精品v日韩精品| 国产精品嫩草99av在线| 国产亚洲精品v| 亚洲国产精品久久久久秋霞不卡| 亚洲人成在线播放| 在线视频亚洲| 欧美综合第一页| 久久久无码精品亚洲日韩按摩| 农夫在线精品视频免费观看| 亚洲国产精品久久久久| 一区二区黄色| 欧美一区二区三区四区在线观看地址 | 亚洲精品在线观看视频| 亚洲香蕉伊综合在人在线视看| 性久久久久久久| 免费h精品视频在线播放| 亚洲区第一页| 欧美一区视频| 欧美精品v日韩精品v韩国精品v| 国产精品久久久久久久久| 国内精品美女在线观看| 99精品国产在热久久婷婷| 午夜日韩av| 欧美激情欧美狂野欧美精品| 一区二区久久久久久| 久久国产精品一区二区| 欧美日本久久| 国产一区视频观看| av成人免费在线观看| 久久久91精品国产| 亚洲乱码国产乱码精品精天堂 | 亚洲国产精品成人精品| 亚洲一区二区三区精品视频| 另类春色校园亚洲| 一区二区三区日韩| 裸体一区二区| 国产日韩一级二级三级| 夜夜精品视频一区二区| 老牛影视一区二区三区| 亚洲一二区在线| 欧美国产免费| 极品尤物av久久免费看 | 久久爱另类一区二区小说| 亚洲国产精品传媒在线观看| 欧美在线观看视频在线| 嫩草影视亚洲| 永久域名在线精品| 91久久夜色精品国产九色| 午夜一区不卡| 亚洲精品综合在线| 六十路精品视频| 国产一区久久| 香蕉久久夜色精品| 99re热精品| 欧美国产激情二区三区| 在线观看日韩欧美| 久久精品人人做人人爽电影蜜月| 日韩视频免费观看| 欧美高清在线一区| 136国产福利精品导航| 久久精品国产亚洲一区二区| 国产精品99久久99久久久二8| 欧美人妖在线观看| 亚洲啪啪91| 亚洲电影免费观看高清完整版在线 | 国产精品亚洲不卡a| 亚洲一本大道在线| 亚洲精品乱码久久久久久日本蜜臀| 久久综合色88| 亚洲国产精品va在看黑人| 毛片av中文字幕一区二区| 久久国产加勒比精品无码| 国产婷婷一区二区| 久久国产精品一区二区三区四区| 亚洲一区二区三区精品视频 | 先锋资源久久| 亚洲午夜久久久久久久久电影院| 欧美日韩一区二区三区四区五区 | 99在线视频精品| 亚洲黄色免费电影| 欧美激情亚洲综合一区| 亚洲免费观看视频| 亚洲人午夜精品| 欧美日韩午夜剧场| 亚洲欧美激情一区二区| 亚洲一级黄色| 国产亚洲综合性久久久影院| 久久青草欧美一区二区三区| 久久婷婷综合激情| 亚洲欧洲日产国产综合网| 亚洲精品乱码久久久久久久久| 欧美日韩国产一区| 亚洲欧美日韩精品在线| 亚洲欧美自拍偷拍| 在线观看精品视频| 亚洲二区视频在线| 欧美日韩亚洲天堂| 欧美一区二区在线看| 久久精品男女| 亚洲人成7777| 一区二区三区视频观看| 国产午夜精品久久| 欧美国产日本在线| 欧美三级在线| 久久精品国产视频| 欧美成人精品| 亚洲欧美国产va在线影院| 久久精品成人欧美大片古装| 亚洲精品久久久蜜桃| 亚洲无限乱码一二三四麻| 激情小说亚洲一区| aⅴ色国产欧美|