樹狀數(shù)組套主席樹維護DFS序

網(wǎng)上linux交不過，windows下測可以，linux下Re

大家打check用吧

#include <cstdio> #include <cstring> #include <cstdlib> #include <cmath> #include <ctime> #include <iostream> #include <algorithm> #include <stack> #include <deque> #include <queue> #include <map> #define max( x , y ) ( ( x ) > ( y ) ? ( x ) : ( y ) ) #define min( x , y ) ( ( x ) < ( y ) ? ( x ) : ( y ) ) const int max_int = ( 2147483467 ) , oo = ( 1e9 ) ; #define FOR( TMP , ST , ED ) for ( int TMP = ( ST ) ; TMP < ( ED ) ; TMP ++ ) #define FORD( TMP , ST , ED ) for ( int TMP = ( ST ) ; TMP > ( ED ) ; TMP -- ) using namespace std ; // yzx's Rp ++const int maxn = ( 8 * 1e4 + 10 ) , max_depth = ( 19 ) ; struct Question_node{int Kth , L , R , Lca ;} Qt[ maxn ] ; struct state_node{int Ch[ 2 ] , sum , Last ;} Tr[ 9780000 ] ; int Root[ maxn ] , Rot[ maxn ] , Tot ; int Begin[ maxn ] , End[ maxn ] , Tim , Father[ maxn ] , Fa[ maxn ] ; int first[ maxn << 1 ] , To[ maxn << 2 ] , Nex[ maxn << 2 ] , Val[ maxn << 2 ] , Len ; int N , M ; int data[ maxn << 1 ] , Len_data , back[ maxn << 1 ] , Sum ; int An[ maxn ] , QQ[ maxn ] ;inline void ins( int x , int y ) {To[ Len ] = y , Nex[ Len ] = first[ x ] ;first[ x ] = Len ++ ;return ; }inline bool Cmp( int A , int B ) {return ( data[ A ] < data[ B ] ) ; } inline void LiSanHua() {FOR ( i , 0 , Len_data ) Rot[ i ] = i ;sort( Rot , Rot + Len_data , Cmp ) ;int last = - max_int ; Sum = - 1 ;FOR ( i , 0 , Len_data ){if ( last != data[ Rot[ i ] ] ) Sum ++ ;back[ Sum ] = last = data[ Rot[ i ] ] ;data[ Rot[ i ] ] = Sum ;}return ; }inline void Updata( int now , int val , int cost ) {int L = 0 , R = Sum , mid , type ;Tr[ now ].sum += cost ;while ( L < R ){mid = ( L + R ) >> 1 ;if ( val <= mid ) R = mid , type = 0 ;else L = mid + 1 , type = 1 ;if ( Tr[ Tr[ now ].Ch[ type ] ].Last != now ){Tr[ Tot ++ ] = Tr[ Tr[ now ].Ch[ type ] ] ;Tr[ Tr[ now ].Ch[ type ] = ( Tot - 1 ) ].sum += cost ;Tr[ Tr[ now ].Ch[ type ] ].Last = now ;now = Tr[ now ].Ch[ type ] ;}else{Tr[ Tr[ now ].Ch[ type ] ].sum += cost ;now = Tr[ now ].Ch[ type ] ;}}return ; }bool vis[ maxn ] ; inline int Find( int x ) {int T ;for ( T = x ; Fa[ T ] != T ; ) T = Fa[ T ] ;return Fa[ x ] = T ; } inline void DFS( int x ) {Fa[ x ] = x , vis[ x ] = 1 ;Root[ Begin[ x ] = Tim ++ ] = Tot ++ ;Tr[ Root[ Begin[ x ] ] ] =Tr[ Father[ x ] > - 1 ? Root[ Begin[ Father[ x ] ] ] : 0 ] ;Updata( Root[ Begin[ x ] ] , data[ x ] , 1 ) ;int tab , u ;for ( tab = first[ x ] ; tab != - 1 ; tab = Nex[ tab ] )if ( ( u = To[ tab ] ) != Father[ x ] ){Father[ u ] = x ;DFS( u ) ;Fa[ Find( u ) ] = Find( x ) ;}End[ x ] = Tim ;for ( tab = first[ x + N ] ; tab != - 1 ; tab = Nex[ tab ] )if ( vis[ u = To[ tab ] ] )Qt[ Val[ tab ] ].Lca = Find( u ) ;return ; }int Left[ max_depth << 2 ] , Right[ max_depth << 2 ] ; #define lowbit( x ) ( ( x ) & ( - ( x ) ) ) inline void Get( int x , int *T ) {if ( x >= 0 ){x = Begin[ x ] ;T[ ++ T[ 0 ] ] = Root[ x ] ;for ( ; ( x + 1 ) > 0 ; x -= lowbit( x + 1 ) ) T[ ++ T[ 0 ] ] = Rot[ x ] ;}return ; } inline int solve( int K ) {int L = 0 , R = Sum , mid , type , cnt , T_cnt ;while ( L < R ){cnt = T_cnt = 0 ;FOR ( i , 1 , Right[ 0 ] + 1 )cnt += Tr[ Tr[ Right[ i ] ].Ch[ 1 ] ].sum , T_cnt += Tr[ Right[ i ] ].sum ;FOR ( i , 1 , Left[ 0 ] + 1 )cnt -= Tr[ Tr[ Left[ i ] ].Ch[ 1 ] ].sum , T_cnt -= Tr[ Left[ i ] ].sum ;mid = ( L + R ) >> 1 ;if ( T_cnt < K ) break ;if ( cnt >= K ) type = 1 , L = mid + 1 ;else type = 0 , R = mid ;FOR ( i , 1 , Left[ 0 ] + 1 ) Left[ i ] = Tr[ Left[ i ] ].Ch[ type ] ;FOR ( i , 1 , Right[ 0 ] + 1 ) Right[ i ] = Tr[ Right[ i ] ].Ch[ type ] ;K -= !type * cnt ;}return L == R ? R : - 1 ; }inline void Change( int x , int val , int cost ) {for ( ; ( x + 1 ) <= N ; x += lowbit( x + 1 ) )Updata( Rot[ x ] , val , cost ) ;return ; } int main() {freopen( "network.in" , "r" , stdin ) , freopen( "network.out" , "w" , stdout ) ;scanf( "%d%d" , &N , &M ) ;memset( first , 255 , sizeof( int ) * N ) , Len = 0 ;FOR ( i , 0 , N ) scanf( "%d" , &data[ i ] ) ;FOR ( i , 1 , N ){int Fr , En ;scanf( "%d%d" , &Fr , &En ) ;ins( Fr - 1 , En - 1 ) , ins( En - 1 , Fr - 1 ) ;}Len_data = N ;memset( first + N , 255 , sizeof( int ) * N ) ;QQ[ 0 ] = 0 , memset( An , 0 , sizeof( int ) * N ) ;FOR ( i , 0 , M ){scanf( "%d%d%d" , &Qt[ i ].Kth , &Qt[ i ].L , &Qt[ i ].R ) ;if ( !Qt[ i ].Kth ){if ( An[ Qt[ i ].L - 1 ] == 0 ){data[ Len_data ++ ] = Qt[ i ].R ;Qt[ i ].L -- , Qt[ i ].R = Len_data - 1 ;An[ Qt[ i ].L ] = Qt[ i ].R , QQ[ ++ QQ[ 0 ] ] = Qt[ i ].L ;}else{data[ An[ Qt[ i ].L - 1 ] ] = Qt[ i ].R ;Qt[ i ].L -- ;Qt[ i ].R = An[ Qt[ i ].L ] ;}}else{Qt[ i ].L -- , Qt[ i ].R -- ;ins( Qt[ i ].L + N , Qt[ i ].R ) , Val[ Len - 1 ] = i ;ins( Qt[ i ].R + N , Qt[ i ].L ) , Val[ Len - 1 ] = i ;FOR ( j , 1 , QQ[ 0 ] + 1 ) An[ QQ[ j ] ] = 0 ;QQ[ 0 ] = 0 ;}}LiSanHua() ;Tot = 1 ;FOR ( i , 0 , N ) Rot[ i ] = Tot ++ ;memset( vis , 0 , sizeof( bool ) * N ) , Father[ 0 ] = - 1 , Tim = 0 ;DFS( 0 ) ;FOR ( i , 0 , M )if ( Qt[ i ].Kth ){Left[ 0 ] = Right[ 0 ] = 0 ;Get( Qt[ i ].L , Right ) , Get( Qt[ i ].R , Right ) ;Get( Qt[ i ].Lca , Left ) , Get( Father[ Qt[ i ].Lca ] , Left ) ;int Ans = solve( Qt[ i ].Kth ) ;if ( Ans > - 1 ) cout << back[ Ans ] << endl ;else cout << "invalid request!" << endl ;}else{Change( Begin[ Qt[ i ].L ] , data[ Qt[ i ].L ] , - 1 ) ;Change( End[ Qt[ i ].L ] , data[ Qt[ i ].L ] , 1 ) ;Change( Begin[ Qt[ i ].L ] , data[ Qt[ i ].R ] , 1 ) ;Change( End[ Qt[ i ].L ] , data[ Qt[ i ].R ] , - 1 ) ;data[ Qt[ i ].L ] = data[ Qt[ i ].R ] ;}return 0 ; }

轉(zhuǎn)載于:https://www.cnblogs.com/yzxshuaige123/archive/2013/04/23/3037820.html

創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎勵來咯，堅持創(chuàng)作打卡瓜分現(xiàn)金大獎

總結(jié)

以上是生活随笔為你收集整理的bzoj1146CTSC2008Network的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。