// 平衡树 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 ); }