Splay 删除、插入、翻转

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <vector>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>
using namespace std ;

#pragma comment(linker, "/STACK:1024000000,1024000000")
#define KEY_TREE ch[ ch[root][1] ][0]
#define lson l , m , rt<<1
#define rson m+1 , r , rt<<1|1
#define lowbit(x)  (x&(-x))
#define pb push_back

template<typename T> T Max( T a , T b ) { return a > b ? a : b ; }
template<typename T> T Min( T a , T b ) { return a < b ? a : b ; }
template<typename T> T Abs( T A ) { return A > 0 ? A : -1*A ; }
template<typename T>void Swap( T &a , T &b) { T tmp = a ; a=b ; b = tmp ; }

typedef pair<int , int> pii ;
typedef long long llong ;

const llong LINF = 0x3FFFFFFFFFFFFFFLL ;
const int INF = 0X3FFFFFFF ;
const int MAXN = 1000005 ;
int a[MAXN] ;

class SplayTree
{
    public :
        void PushUp( int rt ) ;
        void PushDown( int rt ) ;

        void Build( int &rt , int left, int right , int fa ) ;
        void NewNode( int &rt , int nd_val , int fa ) ;
        void Init(const int &n) ;

        void Rotate( int x , int col ) ;
        void Splay( int rt , int goal ) ;
        void RotateTo( int k , int goal ) ;

        void Reversal( int pos , int k ) ;
        void Insert( int pos , int nd_val ) ;
        void Delete( int pos , int k ) ;

        void InOrder( int rt , int &cnt ) ;
        void Print( const int &n ) ;

    private :
        int ch[MAXN][2] ;
        int val[MAXN] , sz[MAXN] , pre[MAXN] ;
        bool rev[MAXN] ;
        int root , top ;
} spt ;

inline void SplayTree::PushUp( int rt )
{
    int l = ch[rt][0] , r = ch[rt][1] ;  //************
    sz[rt] = sz[l] + sz[r] +1 ;
}

inline void SplayTree::PushDown( int rt )
{
    if ( rev[rt] )
    {
        int &l = ch[rt][0] , &r = ch[rt][1] ;
        rev[l] ^= 1 , rev[r] ^= 1 ;
        Swap( l , r ) ;
        rev[rt] = 0 ;
    }
}

inline void SplayTree::NewNode(int &rt , int nd_val , int fa)
{
    rt = ++top ;
    rev[rt] = ch[rt][0] = ch[rt][1] =  0 ;
    val[rt] = nd_val ;
    sz[rt] = 1 ;
    pre[rt] = fa ;
}

void SplayTree::Build( int &rt , int left , int right , int fa )
{
    if ( left > right ) return ;
    int m = ( left + right ) >> 1;
    NewNode( rt , a[m] ,fa ) ;
    Build( ch[rt][0] , left , m-1 , rt ) ;
    Build( ch[rt][1] , m+1 , right , rt ) ;
    PushUp( rt ) ;
}

inline void SplayTree::Init( const int &n )
{
    root = top = 0 ;
    ch[root][0] = ch[root][1] = rev[root] = pre[root] = sz[root] = 0 ;
    NewNode( root , -100 , 0 ) ;
    NewNode( ch[root][1] , -1, root ) ;
    PushUp( root ) ;
    Build( KEY_TREE , 1 , n , ch[root][1] ) ;
    PushUp( ch[root][1] ) ;
    PushUp( root ) ;
}

inline void SplayTree::Rotate( int x , int col )
{
    int y = pre[x] ;
    PushDown( y ) ;
    PushDown( x ) ;
    ch[y][!col] = ch[x][col] ;
    pre[ ch[x][col] ] = y ;
    if ( pre[y] )
        ch[ pre[y] ][ ch[ pre[y] ][1] == y ] = x ;  //***************
    pre[x] = pre[y] ;
    pre[y] = x ;
    ch[x][col] = y ;
    PushUp( y ) ;
}

void SplayTree::Splay( int rt , int goal )
{
    PushDown( rt ) ;
    while ( pre[rt] != goal )
    {
        if ( pre[ pre[rt] ] == goal )
            Rotate( rt , ch[ pre[rt] ][0] == rt ) ;
        else
        {
            int y = pre[rt] ;
            int col = ( ch[ pre[y] ][0] == y ) ;

            if ( ch[y][col] == rt )  //***********
                Rotate( rt , !col ) ;
            else
                Rotate( y , col ) ;
            Rotate( rt , col ) ;
        }
    }
    PushUp( rt ) ;
    if ( goal == 0 ) root = rt ;
}

inline void SplayTree::RotateTo(int k , int goal )
{
    int x = root ;
    PushDown( x ) ;
    while ( sz[ ch[x][0] ] +1 != k )
    {
        if ( sz[ ch[x][0] ] >= k )
            x = ch[x][0] ;
        else
        {
            k = k - sz[ ch[x][0] ] - 1 ;
            x = ch[x][1] ;
        }
        PushDown(x) ;
    }
    Splay( x , goal ) ;
}

inline void SplayTree::Reversal( int pos , int k )
{
    RotateTo( pos , 0 ) ;
    RotateTo( pos+k+1 , root ) ;
    rev[KEY_TREE] ^= 1;
}

inline void SplayTree::Insert( int pos , int nd_val )
{
    RotateTo( pos , 0 ) ;
    RotateTo( pos+1 , root ) ;
    NewNode( KEY_TREE , nd_val , ch[root][1] ) ;
    PushUp( ch[root][1] ) ;
    PushUp( root ) ;
}

inline void SplayTree::Delete( int pos , int k )
{
    RotateTo( pos , 0 ) ;
    RotateTo( pos+k+1 , root ) ;
    KEY_TREE = 0 ;
    PushUp( ch[root][1] ) ;
}

void SplayTree::InOrder( int rt , int &cnt )
{
    if ( rt == 0 ) return ;
    PushDown(rt) ;  //*************
    InOrder( ch[rt][0] , cnt ) ;
    if ( cnt ) putchar(' ') ;
    printf("%d" , val[rt] ) ;
    InOrder( ch[rt][1] , ++cnt ) ;
}

inline void SplayTree::Print( const int &n )
{
    RotateTo( 1 , 0 ) ;
    RotateTo( n+2 , root ) ;
    int cnt = 0 ;
    InOrder( KEY_TREE , cnt ) ;
    puts("") ;
}

int main()
{
    int T ;
    scanf( "%d", &T ) ;
    for ( int nca = 1; nca <= T ; nca++ )
    {
        int n ;
        scanf("%d", &n) ;
        for ( int i = 1 ; i <= n; i++ )
            scanf("%d", a+i) ;

        spt.Init( n ) ;
        char opt[20] ;
        const int k = 1 ;
        int posl , posr , Q ;
        scanf( "%d%d%d", &posl , &posr , &Q ) ;

        while ( Q-- )
        {
            scanf( "%s" , opt ) ;

            if ( opt[0] == 'M' && opt[4] == 'L' )
            {
                scanf( "%s" , opt ) ;
                if ( opt[0] == 'L' ) posl-- ;
                else posr-- ;
            }
            else if ( opt[0] == 'M' && opt[4] == 'R'  )
            {
                scanf( "%s" , opt ) ;
                if ( opt[0] == 'L' ) posl++ ;
                else posr++ ;
            }
            else if ( opt[0] == 'I' )
            {
                scanf( "%s" , opt ) ;
                scanf( "%d" , &a[1] ) ;
                if ( opt[0] == 'L' ) spt.Insert( posl , a[1] ) ;
                else spt.Insert( posr+1 , a[1] ) ;
                n++ , posr++ ;
            }
            else if ( opt[0] == 'R' )
            {
                spt.Reversal( posl , posr- posl+1 ) ;
            }
            else if ( opt[0] == 'D' )
            {
                scanf( "%s" , opt ) ;
                if ( opt[0] == 'L' )
                    spt.Delete( posl , 1 ) ;
                else spt.Delete( posr , 1 ) ;
                n-- , posr-- ;
            }

        }
        spt.Print( n ) ;
    }
    return 0 ;
}