HDU 4251 The Famous ICPC Team Again-白红宇

HDU 4251 The Famous ICPC Team Again

阅读量：5788 次

发布时间：2019-06-18

本文共 2189 字，大约阅读时间需要 7 分钟。

这个也是一道对划分树的简单的运用：

View Code

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             #include
              
               #include
               
                using namespace std;class Node{public: int num[100024],val[100024]; }node[20];int val[100024];bool cmp( int a , int b ){ return a <= b;}void build_tree( int l , int r , int deep ){ if( l == r ) return ; int mid = ( l + r )>>1; int issame = mid - l + 1 ,same = 0; for( int i = l ; i <= r ; i ++ ) if( node[deep].val[i] < val[mid] ) issame --; int left = l ,right = mid + 1; for( int i = l ; i <= r ; i ++ ) { node[deep].num[i] = node[deep].num[i-1]; if( node[deep].val[i] > val[mid] ) node[deep+1].val[right++] = node[deep].val[i]; else if( node[deep].val[i] < val[mid] ) { node[deep+1].val[left++] = node[deep].val[i]; node[deep].num[i] ++; } else { if( same < issame ) { same ++; node[deep+1].val[left++] = node[deep].val[i]; node[deep].num[i] ++; } else node[deep+1].val[right++] = node[deep].val[i]; } } build_tree( l , mid , deep + 1 ); build_tree( mid + 1, r ,deep + 1 ); }int find( int a , int b , int k ,int deep, int l ,int r ){ //printf( "l=%d,r=%d,s=%d,t=%d,k=%d,dep=%d\n",l,r,a,b,k,deep);system("pause"); int mid = ( l + r )>>1; if( a == b ) return node[deep].val[a]; int d = node[deep].num[b] - node[deep].num[a-1]; int s = node[deep].num[a-1] - node[deep].num[l-1]; int ss = node[deep].num[b] - node[deep].num[l-1]; int rx = a - l + 1 - s,ry = b - l + 1 - ss; if( d >= k ) return find( l + s , l + ss - 1 ,k , deep + 1, l , mid ); else return find( mid + rx , mid + ry , k - d , deep + 1 , mid + 1 , r );}int main( ){ int n,m,Case=1,l,r; while( scanf( "%d",&n )==1 ) { for( int i = 1 ; i <= n ; i ++ ) { scanf( "%d",&node[0].val[i] ); val[i] = node[0].val[i]; } sort( val+1, val + n + 1, cmp ); build_tree( 1 , n , 0 ); // printf( "sfaf" ); scanf( "%d",&m ); printf( "Case %d:\n",Case++ ); for( int i = 0 ; i < m ; i ++ ) { scanf( "%d %d",&l,&r ); int k = ( r - l )/2 + 1 ; printf( "%d\n",find( l , r , k, 0 , 1, n ) ); } } //system( "pause" ); return 0;}