hdu 4453 Looploop (伸展树)
hdu 4453 Looploop (伸展树)
题意：给出一个数列，然后又五个操作，维护这个数列.。
解题思路：splay tree 。其实这题就是考你伸展树的基本功了。唯一有点思维的地方，就是move的时候，对于两种move，第一种，把指针逆时针移一位，其实就是把最后一个元素插到最前面，在把最后那个删掉。。。第二种反之。
#include<stdio.h>#include<string.h>#include<algorithm>using namespace std ;const int maxn = 555555 ;int col[maxn] , num[maxn] , val[maxn] , add[maxn] ;int size[maxn] , son[2][maxn] , fa[maxn] , tot ;int k1 , k2 ;void rev ( int rt ) { if ( !rt ) return ; int ls = son[0][rt] , rs = son[1][rt] ; son[1][rt] = ls ; son[0][rt] = rs ; col[rt] ^= 1 ;}void push_up ( int rt ) { size[rt] = 1 ; if ( son[0][rt] ) size[rt] += size[son[0][rt]] ; if ( son[1][rt] ) size[rt] += size[son[1][rt]] ;}void push_down ( int rt ) { int ls = son[0][rt] , rs = son[1][rt] ; if ( add[rt] ) { if ( ls ) add[ls] += add[rt] , val[ls] += add[rt] ; if ( rs ) add[rs] += add[rt] , val[rs] += add[rt] ; add[rt] = 0 ; } if ( col[rt] ) { rev ( ls ) ; rev ( rs ) ; col[rt] = 0 ; }}int new_node ( ) { size[++tot] = 1 ; son[0][tot] = son[1][tot] = 0 , fa[tot] = 0 ; col[tot] = add[tot] = 0 ; return tot ;}int build ( int l , int r ) { if ( l > r ) return 0 ; int mid = l + r >> 1 ; int temp = new_node () ; val[temp] = num[mid] ; son[0][temp] = build ( l , mid - 1 ) ; son[1][temp] = build ( mid + 1 , r ) ; if ( son[0][temp] ) fa[son[0][temp]] = temp , size[temp] += size[son[0][temp]] ; if ( son[1][temp] ) fa[son[1][temp]] = temp , size[temp] += size[son[1][temp]] ; return temp ;}void rot ( int rt , int c ) { int y = fa[rt] , z = fa[y] ; push_down ( y ) , push_down ( rt ) ; son[!c][y] = son[c][rt] ; if ( son[c][rt] ) fa[son[c][rt]] = y ; fa[rt] = z ; if ( z ) { if ( y == son[0][z] ) son[0][z] = rt ; else son[1][z] = rt ; } son[c][rt] = y , fa[y] = rt ; push_up ( y ) ;}void splay ( int x , int to ) { push_down ( x ) ; while ( fa[x] != to ) { if ( fa[fa[x]] == to ) rot ( x , x == son[0][fa[x]] ) ; else { int y = fa[x] , z = fa[y] ; if ( x == son[0][y] ) { if ( y == son[0][z] ) rot ( y , 1 ) , rot ( x , 1 ) ; else rot ( x , 1 ) , rot ( x , 0 ) ; } else { if ( y == son[1][z] ) rot ( y , 0 ) , rot ( x , 0 ) ; else rot ( x , 0 ) , rot ( x , 1 ) ; } } } push_up ( x ) ;}int find ( int rt , int key ) { push_down ( rt) ; int cnt = 0 ; if ( son[0][rt] ) cnt = size[son[0][rt]] ; if ( cnt + 1 == key ) return rt ; if ( cnt + 1 > key ) return find ( son[0][rt] , key ) ; return find ( son[1][rt] , key - cnt - 1 ) ;}int insert ( int l , int x , int rt ) { int temp = find ( rt , l ) ; splay ( temp , 0 ) ; rt = temp ; temp = find ( rt , l + 1 ) ; splay ( temp , rt ) ; int t = new_node () ; val[t] = x ; son[0][temp] = t , fa[t] = temp ; push_up ( temp ) ; push_up ( rt ) ; return rt ;}int del ( int l , int r , int rt ) { int temp = find ( rt , l - 1 ) ; splay ( temp , 0 ) ; rt = temp ; temp = find ( rt , r + 1 ) ; splay ( temp , rt ) ; son[0][temp] = 0 ; push_up ( temp ) ; push_up ( rt ) ; return rt ;}void print ( int rt ) { push_down ( rt ) ; if ( son[0][rt] ) print ( son[0][rt] ) ; printf ( "%d " , val[rt] ) ; if ( son[1][rt] ) print ( son[1][rt] ) ;}int main () { int n , m , i , j , k , x , ca = 0 ; char s[111] ; while ( scanf ( "%d%d%d%d" , &n , &m , &k1 , &k2 ) != EOF ) { if ( n == 0 ) break ; for ( i = 1 ; i <= n ; i ++ ) scanf ( "%d" , &num[i] ) ; printf ( "Case #%d:\n" , ++ ca ) ; tot = 0 ; int rt = build ( 0 , n + 1 ) ; while ( m -- ) { scanf ( "%s" , s ) ; if ( s[0] == 'q' ) { int temp = find ( rt , 2 ) ; splay ( temp , 0 ) ; rt = temp ; printf ( "%d\n" , val[rt] ) ; } else if ( s[0] == 'r' ) { int temp = find ( rt , 1 ) ; splay ( temp , 0 ) ; rt = temp ; temp = find ( rt , 2 + k1 ) ; splay ( temp , rt ) ; rev ( son[0][temp] ) ; } else if ( s[0] == 'i' ) { scanf ( "%d" , &x ) ; rt = insert ( 2 , x , rt ) ; } else if ( s[0] == 'd' ) { rt = del ( 2 , 2 , rt ) ; } else if ( s[0] == 'a' ) { scanf ( "%d" , &x ) ; int temp = find ( rt , 1 ) ; splay ( temp , 0 ) ; rt = temp ; temp = find ( rt , k2 + 2 ) ; splay ( temp , rt ) ; int fuck = son[0][temp] ; val[fuck] += x ; add[fuck] += x ; push_up ( temp ) ; push_up ( rt ) ; } else { scanf ( "%d" , &x ) ; if ( x == 2 ) { int temp = find ( rt , 2 ) ; temp = val[temp] ; rt = del ( 2 , 2 , rt ) ; int len = size[rt] ; rt = insert ( len - 1 , temp , rt ) ; } else { int len = size[rt] ; int temp = find ( rt , len - 1 ) ; temp = val[temp] ; rt = del ( len - 1 , len - 1 , rt ) ; rt = insert ( 1 , temp , rt ) ; } } } } return 0 ;}