其实我只是来存一下我的splay模板的。。请大牛们多多指教
#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]] ) ;
}
}
}
}