• <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>
            

    
            

            




            







												


        


            


            coreBugZJ
            

            此 blog 已棄。
            

            




            
	
					
	
            
		
            
			歸并樹(shù)
		
            
		
            記錄歸并排序的中間結(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 閱讀(1797) 評(píng)論(0)  編輯 收藏 引用  所屬分類(lèi): DataStructure 
		
            
	
            
	
	





            
	    
    




            






            

				

            


    
    







            
	   
	



久久久国产乱子伦精品作者|
国产精品久久一区二区三区|
精品国产青草久久久久福利|
97超级碰碰碰久久久久|
亚洲精品无码久久久久AV麻豆|
国产成人久久精品一区二区三区|
久久99国产精一区二区三区|
日日狠狠久久偷偷色综合免费
|
热久久最新网站获取|
无码人妻久久一区二区三区|
91精品国产91久久|
久久久久久人妻无码|
欧美精品丝袜久久久中文字幕|
蜜臀久久99精品久久久久久小说|
久久久精品日本一区二区三区
|
国产精品一区二区久久精品无码|
久久精品国产免费观看|
欧美精品一区二区久久|
99国内精品久久久久久久|
久久国产高潮流白浆免费观看|
日本精品久久久久影院日本|
九九久久精品国产|
久久精品国产69国产精品亚洲|
国产亚洲精久久久久久无码77777
国产亚洲精品久久久久秋霞
|
久久se精品一区精品二区|
日韩乱码人妻无码中文字幕久久|
久久最新免费视频|
久久精品一区二区三区中文字幕|
99久久精品国产麻豆|
av国内精品久久久久影院|
久久久女人与动物群交毛片|
久久精品中文字幕一区|
日韩精品久久久久久久电影|
一本久久免费视频|
亚洲国产成人精品女人久久久
|
俺来也俺去啦久久综合网|
日韩久久久久久中文人妻|
色婷婷综合久久久中文字幕|
狠狠精品久久久无码中文字幕|
久久精品国产久精国产果冻传媒
|
99国产精品久久|