hdu 1754 I Hate It (splay tree伸展樹)

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std ;

const int maxn = 222222 ;

int son[2][maxn] , col[maxn] , fa[maxn] , size[maxn] , val[maxn] ;
int tot ;
int num[maxn] ;

void new_node () {
	size[tot] = 1 ;
	fa[tot] = son[0][tot] = son[1][tot] = -1 ;
	val[tot] = col[tot] = 0 ;
	tot ++ ;
}

void update ( int rt ) {
	size[rt] = 1 ;
	col[rt] = val[rt] ;
	if ( son[0][rt] != -1 ) 
		size[rt] += size[son[0][rt]] , col[rt] = max ( col[rt] , col[son[0][rt]] ) ;
	if ( son[1][rt] != -1 )
		size[rt] += size[son[1][rt]] , col[rt] = max ( col[rt] , col[son[1][rt]] ) ;
}

int build ( int l , int r ) {
	if ( l > r ) return -1 ;
	int mid = ( l + r ) >> 1 ;
	new_node () ;
	int temp = tot - 1 ;
	val[temp] = num[mid] ;
	son[0][temp] = build ( l , mid - 1 ) ;  
	if ( son[0][temp] != -1 ) fa[son[0][temp]] = temp ;
	son[1][temp] = build ( mid + 1 , r ) ;
	if ( son[1][temp] != -1 ) fa[son[1][temp]] = temp ;
	update ( temp ) ;
	return temp ;
}

void rot ( int rt , int c ) {
	int y = fa[rt] , z = fa[y] ;
	son[!c][y] = son[c][rt] ;
	if ( son[c][rt] != -1 ) fa[son[c][rt]] = y ;
	fa[rt] = z ;
	if ( z != -1 ) {
		if ( y == son[0][z] ) son[0][z] = rt ;
		else son[1][z] = rt ;
	}
	son[c][rt] = y , fa[y] = rt ;
	update ( y ) ;
}

void splay ( int rt , int to ) {
	while ( fa[rt] != to ) {
		if ( fa[fa[rt]] == to ) {
			if ( rt == son[0][fa[rt]] ) rot ( rt , 1 ) ;
			else rot ( rt , 0 ) ;
		}
		else {
			int y = fa[rt] , z = fa[y] ;
			if ( rt == son[0][y] ) {
				if ( y == son[0][z] ) rot ( y , 1 ) , rot ( rt , 1 ) ;
				else rot ( rt , 1 ) , rot ( rt , 0 ) ;
			}
			else {
				if ( y == son[1][z] ) rot ( y , 0 ) , rot ( rt , 0 ) ;
				else rot ( rt , 0 ) , rot ( rt , 1 ) ;
			}
		}
	}
	update ( rt ) ;
	/*為什麼只要在最後更新rt節點呢？因為在旋轉的過程中，fa[rt]總是旋到rt下面的
	所以在旋轉的時候，我們不斷的更新fa[rt]，而不需要一直更新rt，只要在splay之後更新rt就好了
	*/
}

int find ( int rt , int key ) {
	int cnt = 0 ;
	if ( son[0][rt] != -1 ) cnt = size[son[0][rt]] ;
	if ( cnt + 1 == key ) return rt ;
	if ( cnt >= key ) return find ( son[0][rt] , key ) ;
	return find ( son[1][rt] , key - cnt - 1 ) ;
}

int main () {
	int n , m , i , j , k , a , b ;
	char op[11] ;
	while ( scanf ( "%d%d" , &n , &m ) != EOF ) {
		for ( i = 1 ; i <= n ; i ++ ) scanf ( "%d" , &num[i] ) ;
		tot = 0 ;
		int root = build ( 0 , n + 1 ) , temp ;
		while ( m -- ) {
			scanf ( "%s%d%d" , op , &a , &b ) ;
			a ++ , b ++ ;//因為建樹的時候，把0也建進去了，但實際上0是不在原數組中的，所有往後推移一位
			if ( op[0] == 'U' ) {
				temp = find ( root , a ) ;
				splay ( temp , -1 ) ;
				root = temp ;
				val[root] = b - 1 ;
			//	update ( root ) ;
			//這裡為什麼不用更新rt呢？因為對於size的值是不會變的，而val值已經更新了，而對於col值，下次是splay時，肯定會更新掉的
			}
			else {
				temp = find ( root , a - 1 ) ;
				splay ( temp , -1 ) ;
				root = temp ;
				temp = find ( root , b + 1 ) ;
				splay ( temp , root ) ;
				printf ( "%d\n" , col[son[0][temp]] ) ;
			}
		}
	}
}