Splay 模板
struct SplayTree{
const static int maxn = 1e5 + 15;
int ch[maxn][2] , key[maxn] , s[maxn] , tot , root , fa[maxn];
void init( int x , int val = 0 , int par = 0 ){
ch[x][0]=ch[x][1]=0 , fa[x]= par , key[x] = val , s[x] = 1;
}
void init(){
init( 0 , 0 , 0 ); s[0] = 0;
tot = root = 0 ;
}
inline void up(int x){
s[x] = s[ch[x][0]] + s[ch[x][1]] + 1;
}
void rotate( int x, int d ){
int y = fa[x];
ch[y][d ^ 1] = ch[x][d];
if ( ch[x][d]) fa[ch[x][d]] = y;
fa[x] = fa[y];
if (fa[y]){
if (y == ch[fa[y]][d]) ch[fa[y]][d] = x;
else ch[fa[y]][d ^ 1] = x;
}
ch[x][d] = y , fa[y] = x;
up( y ) , up( x );
}
// Splay x to target's son
void Splay( int x , int target ){
while( fa[x] != target ){
int y = fa[x];
if( x == ch[y][0] ){
if( fa[y] != target && y == ch[fa[y]][0])
rotate( y , 1 );
rotate( x , 1 );
}else{
if( fa[y] != target && y == ch[fa[y]][1])
rotate( y , 0 );
rotate( x , 0 );
}
}
if( !target ) root = x;
}
void Insert( int & t , int val , int par = 0 ){
if( t == 0 ){
t = ++ tot;
init( t , val , par );
Splay( tot , 0 );
}else{
int cur = t;
if( val < key[t] ) Insert( ch[t][0] , val , cur );
else Insert( ch[t][1] , val , cur );
up( cur );
}
}
// Return point
int find( int t , int v ){
if( t == 0 ) return 0;
else if( key[t] == v ){
Splay( t , 0 );
return t;
}
else if( v < key[t] ) return find( ch[t][0] , v );
return find( ch[t][1] , v );
}
// Delete Root
void Delete(){
if( !ch[root][0] ){
fa[ ch[root][1] ] = 0 ;
root = ch[root][1];
}else{
int cur = ch[root][0];
while( ch[cur][1] ) cur = ch[cur][1];
Splay( cur , root );
ch[cur][1] = ch[root][1];
root = cur , fa[cur] = 0 , fa[ch[root][1]] = root;
up( root );
}
}
int size(){
return s[root];
}
// 查第 k 小 , 必须保证合法
int kth( int x , int k ){
if( k == s[ch[x][0]] + 1 ){
Splay( x , 0 );
return key[x];
}
else if( k <= s[ch[x][0]] ) return kth( ch[x][0] , k );
else return kth( ch[x][1] , k - s[ch[x][0]] - 1 );
}
//找前驱
int pred( int t , int v ){
if( t == 0 ) return v;
else{
if( v <= key[t] ) return pred( ch[t][0] , v );
else{
int ans = pred( ch[t][1] , v );
if( ans == v ){
ans = key[t];
Splay( t , 0 );
}
return ans;
}
}
}
/*int less( int t , int v ){
if( t == 0 ) return 0;
int rs = 0;
if( v <= key[t] ) rs = less( ch[t][0] , v );
else rs = s[ch[t][0]] + 1 + less( ch[t][1] , v );
if( Tl ){
Splay( t , 0 );
Tl = 0;
}
return rs;
}*/
//找后继
int succ( int t , int v ){
if( t == 0 ) return v;
else{
if( v >= key[t] ) return succ( ch[t][1] , v );
else{
int ans = succ( ch[t][0] , v );
if( ans == v ){
ans = key[t];
Splay( t , 0 );
}
return ans;
}
}
}
void Preorder( int t ){
if( !t ) return;
Preorder( ch[t][0] );
printf("%d " , key[t] );
Preorder( ch[t][1] );
}
}splay;