bzoj1146: [CTSC2008]网络管理Network

我用的是恶心的竹席（zhuxi擦，尽然是禁忌词）树

#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 ) printf("%d\n", back[ Ans ]);
			else puts( "invalid request!");
		}
		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 ;
}