hdu 4441 Queue Sequence (伸展树splay+树状数组)
hdu 4441 Queue Sequence (伸展树splay)
题意：就是维护一个数列，总共三个操作。1 insert x操作，在x位置插入一个数列中没出现过的，最小的正整数k，然后再找出k前面有多少个正数(不包括k)，假设为j，那么就找到第j+1个负数，再其前面插入-k（其实题意是说找到第j个负数，然后在距离j尽量远的地方插入-k，转换下就好了）。2 remove x ，把数列中的x 和 -x删除掉 3 query x ，询问(x,-x)区间和。
解题思路：我用的伸展树+树状数组。。树状数组是用来维护未出现的最小的正整数k的。起先全赋为0，查询的时候就找到前缀和等于下标的最大的值，然后+1就是未出现的最小的k了，具体可以看get() 函数。然后伸展树就是维护区间和，另外还要维护一个cnt[]数组，cnt[i]表示 i 的子树下有多少个负数。用于insert操作时，找到k前面有多少个正数，以及第j+1个负数在哪里。这部分在search()函数里面。其他就没什么了。
#include<stdio.h>#include<string.h>#include<algorithm>#define ll __int64using namespace std ;const int maxn = 255555 ;ll sum[maxn] ;int son[2][maxn] , fa[maxn] , size[maxn] ;int val[maxn] , cnt[maxn] ;int p1[maxn] , p2[maxn] ;int tot ;int c[maxn] ;int lowbit ( int x ) { return x & ( -x ) ; }void update ( int pos , int v ) { while ( pos < maxn ) { c[pos] += v ; pos += lowbit ( pos ) ; }}int get () { int i , ans = 0 , add = 0 ; for ( i = 17 ; i >= 0 ; i -- ) { int k = ans + ( 1 << i ) ; if ( k == add + c[k] ) { ans = k , add += c[k] ; } } return ans ;}int new_node ( int v ) { size[++tot] = 1 ; cnt[tot] = ( v < 0 ) ; fa[tot] = son[0][tot] = son[1][tot] = 0 ; sum[tot] = val[tot] = v ; return tot ;}void push_up ( int rt ) { int ls = son[0][rt] , rs = son[1][rt] ; sum[rt] = val[rt] , size[rt] = 1 , cnt[rt] = ( val[rt] < 0 ) ; if ( ls ) { sum[rt] += sum[ls] ; size[rt] += size[ls] ; cnt[rt] += cnt[ls] ; fa[ls] = rt ; } if ( rs ) { sum[rt] += sum[rs] ; size[rt] += size[rs] ; cnt[rt] += cnt[rs] ; fa[rs] = rt ; }}int build ( int l , int r ) { if ( l > r ) return 0 ; int mid = l + r >> 1 ; int temp = new_node ( -11111 ) ; son[0][temp] = build ( l , mid - 1 ) ; son[1][temp] = build ( mid + 1 , r ) ; push_up ( temp ) ; return temp ;}void rot ( int rt , int c ) { int y = fa[rt] , z = fa[y] ; 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 ) { 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 key , int 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 ( key , son[0][rt] ) ; return find ( key - cnt - 1 , son[1][rt] ) ;}int search ( int key , int rt ) { int c = ( val[rt] < 0 ) ; if ( son[0][rt] ) c += cnt[son[0][rt]] ; if ( c == key ) { if ( val[rt] < 0 ) return rt ; else return search ( key , son[0][rt] ) ; } if ( c > key ) return search ( key , son[0][rt] ) ; return search ( key - c , son[1][rt] ) ;}ll query ( int l , int r , int &rt ) { splay ( l , 0 ) ; rt = l ; splay ( r , rt ) ; if ( !son[0][r] ) return 0 ; else return sum[son[0][r]] ;}int insert ( int l , int v , int rt ) { int temp = find ( l , rt ) ; splay ( temp , 0 ) ; rt = temp ; temp = find ( l + 1 , rt ) ; splay ( temp , rt ) ; int p = new_node ( v ) ; fa[p] = temp ; son[0][temp] = p ; push_up ( temp ) ; push_up ( rt ) ; return rt ;}int del ( int l , int r , int rt ) { int temp = find ( l - 1 , rt ) ; splay ( temp , 0 ) ; rt = temp ; temp = find ( r + 1 , rt ) ; splay ( temp , rt ) ; son[0][temp] = 0 ; push_up ( temp ) ; push_up ( rt ) ; return rt ;}void print ( int rt ) { if ( son[0][rt] ) print ( son[0][rt] ) ; printf ( "%d " , val[rt] ) ; if ( son[1][rt] ) print ( son[1][rt] ) ;}int main () { int m , ca = 0 ; while ( scanf ( "%d" , &m ) != EOF ) { tot = 0 ; memset ( c , 0 , sizeof (c ) ) ; int rt = build ( 0 , 1 ) ; int x ; char s[222] ; printf ( "Case #%d:\n" , ++ ca ) ; while ( m -- ) { scanf ( "%s" , s ) ; scanf ( "%d" , &x ) ; if ( s[0] == 'i' ) { int k = get () + 1 ; rt = insert ( x + 1 , k , rt ) ; int temp = son[0][son[1][rt]] ; p1[k] = temp ; splay ( temp , 0 ) ; rt = temp ; int fuck = x + 1 - ( son[0][rt] ? cnt[son[0][rt]] : 0 ) ; temp = search ( fuck + 2 , rt ) ; splay ( temp , 0 ) ; rt = temp ; rt = insert ( size[son[0][rt]] , -k , rt ) ; temp = son[0][son[1][rt]] ; p2[k] = temp ; update ( k , 1 ) ; } else if ( s[0] == 'r' ) { int a = p1[x] , b = p2[x] ; update ( x , -1 ) ; splay ( a , 0 ) ; rt = a ; x = size[son[0][rt]] + 1 ; rt = del ( x , x , rt ) ; splay ( b , 0 ) ; rt = b ; x = size[son[0][rt]] + 1 ; rt = del ( x , x , rt ) ; } else if ( s[0] == 'q' ) { int l = p1[x] , r = p2[x] ; printf ( "%I64d\n" , query ( l , r , rt ) ) ; } } } return 0 ;}/*100000i 0i 2i 0*/