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





            
	    
    




            






            

				

            


    
    







            
	   
	



性做久久久久久久久老女人|
欧美精品乱码99久久蜜桃|
国产毛片欧美毛片久久久|
国产一区二区精品久久凹凸|
精品国产一区二区三区久久久狼|
日本久久中文字幕|
久久91精品综合国产首页|
久久精品国产99国产电影网|
久久国产色AV免费观看|
新狼窝色AV性久久久久久|
99久久香蕉国产线看观香|
天天综合久久一二三区|
久久无码人妻精品一区二区三区|
久久久久久久久久免免费精品|
999久久久国产精品|
精品久久久久中文字|
国产综合精品久久亚洲|
久久精品成人免费观看97|
久久精品国产亚洲一区二区三区|
久久精品国产亚洲7777|
久久久久一本毛久久久|
久久毛片一区二区|
亚洲色欲久久久综合网|
久久w5ww成w人免费|
久久香蕉综合色一综合色88|
国产成人久久精品二区三区|
久久久亚洲精品蜜桃臀|
一本色道久久88综合日韩精品
|
亚洲午夜久久影院|
午夜不卡888久久|
青青热久久国产久精品|
亚洲色大成网站www久久九|
久久久久免费看成人影片|
日本精品久久久久中文字幕8|
久久久久久极精品久久久|
国产69精品久久久久久人妻精品
|
久久ZYZ资源站无码中文动漫
|
91精品国产综合久久香蕉
|
99久久国产宗和精品1上映|
久久久久99精品成人片试看|
久久亚洲欧美日本精品|