BZOJ-1861: [Zjoi2006]Book 书架（spl

题目：http://www.lydsy.com/JudgeOnline/problem.php?id=1861

裸的splay维护即可，之前脑残地忘记在最前和最后加点了，分类地快吐。。。

代码：

2934349b033b5bb51690608734d3d539b600bc00.jpg.png

#include <cstdio>

#include <algorithm>

#include <cstring>

 

using namespace std ;

 

#define MAXN 100010

#define L( t ) left[ t ]

#define R( t ) right[ t ]

#define F( t ) father[ t ]

#define G( t ) F(F( t ))

#define S( t ) size[ t ]

#define update( t ) S( t )=S(L( t ))+S(R( t ))+1

#define clear( t ) memset( t ,0,sizeof( t ))

#define C( t ) (L(F( t ))== t )

 

int left[ MAXN ], right[ MAXN ], father[ MAXN ], size[ MAXN ];

int n , m , a[ MAXN ];

 

void zag(int t ){

    int k =R( t ), u =F( t );bool flag =C( t );

    F(R( t )=L( k ))= t ;update( t );

    F(L( k )= t )= k ;      update( k );

    F( k )= u ;if( u )if( flag )L( u )= k ;else R( u )= k ;

}

 

void zig(int t ){

    int k =L( t ), u =F( t );bool flag =C( t );

    F(L( t )=R( k ))= t ;update( t );

    F(R( k )= t )= k ;      update( t );

    F( k )= u ;if( u )if( flag )L( u )= k ;else R( u )= k ;

}

 

void splay(int t ){

    while(F( t )){

        if(!G( t ))if(C( t ))zig(F( t ));else zag(F( t ))

        ;else{

            if(C( t )){

                if(C(F( t )))zig(G( t ));zig(F( t ));

            }else{

                if(!C(F( t )))zag(G( t ));zag(F( t ));

            }

        }

    }

}

 

int select(int t ,int r ){

    while(1){

        if(S(L( t ))== r )return t ;

        if( r <S(L( t ))) t =L( t );else{

            r -=(S(L( t ))+1);

            t =R( t );

        }

    }

}

 

int rank(int t ){

    splay( t );

    return S(L( t ));

}

 

int Max(int t ){

    for(;R( t ); t =R( t ));

    return t ;

}

 

int Min(int t ){

    for(;L( t ); t =L( t ));

    return t ;

}

 

int cut(int t ){

    splay( t );

    int u =R( t ), w ;F( u )=0;

    splay( w =Min( u ));

    F(L( w )=L( t ))= w ;update( w );

    L( t )=R( t )=0;update( t );

    return w ;

}

 

int main(  ){

    clear( left ),clear( right ),clear( father ),clear( size );

    scanf("%d%d",&n ,&m );

    for(int i =0; i ++< n +2;)S( i )=1;

    for(int i =0; i ++< n ;)scanf("%d",&a[ i ]);

    a[0]= n +1, a[ n +1]= n +2;

    for(int i =0; i ++< n +1;){

        F(L( a[ i ])= a[ i -1])= a[ i ];update( a[ i ]);

    }

    while( m --){

        char s[20];scanf("%s", s );

        int x , y , z , k ;

        switch( s[0]){

            case'T':

                scanf("%d",&x );

                y =cut( x );

                splay( n +1);

                F(R( x )=R( n +1))= x ;update( x );

                F(R( n +1)= x )= n +1;update( n +1);

                break;

            case'B':

                scanf("%d",&x );cut( x );

                splay( n +2);

                F(L( x )=L( n +2))= x ;update( x );

                F(L( n +2)= x )= n +2;update( n +2);

                break;

            case'I':

                scanf("%d%d",&x ,&y );

                z =rank( x )+ y ;

                y =cut( x );

                splay( y );

                splay( k =select( y , z ));

                F(L( x )=L( k ))= x ;update( x );

                F(L( k )= x )= k ;update( k );

                break;

            case'A':

                scanf("%d",&x );

                printf("%d\n",rank( x )-1);

                break;

            case'Q':

                scanf("%d",&x );

                splay(1);

                printf("%d\n",select(1, x ));

                break;

        }

    }

    return 0;

}