【データ構造】ツリースピリット
// splay
void rotate( int i )
{
int D = dad[i], G = dad[D], S = son[i][ !typ[i] ];
son[G][ typ[D] ] = i, dad[S] = D;
son[D][ typ[i] ] = S, dad[D] = i;
son[i][ !typ[i] ] = D, dad[i] = G;
typ[S] = typ[i], typ[i] = typ[D], typ[D] = !typ[S];
update( D );
}
void splay( int i )
{
while( typ[i] != 2 )
{
if( typ[ dad[i] ] != 2 )
if( typ[i] == typ[ dad[i] ] ) rotate( dad[i] ); else rotate( i );
rotate( i );
}
update( i );
}