Treap（名次树）

Treap

满足以下性质：

1.左子树的值比根节点小，右子树的值比根节点大。

2.根节点的优先级满足堆的性质。

Treap的性质的笛卡尔树的性质是一样，只不过Treap中优先级是随机生成的。

Treap相对于平衡二叉树的优点：

1.代码简单，复杂度一般情况下要快。

2.不受平衡因子的约束，删除一个上限区间较方便。

结构体设计：

struct Node { int x, r, cnt; struct Node * ch[2]; int cmp ( int k ) { int d = x-k; if ( d == 0 ) return -1; return d > 0 ? 0 : 1; } void maintain ( ) { cnt = ch[0]->cnt+ch[1]->cnt+1; } }; x为节点值，r为优先级，cnt统计子树节点的个数。

插入节点时，按二叉树的方式插入，最后判断如果插入节点的优先级比根节点的优先级大（假设为大顶堆），如果此节点为左节点进行右旋就能使其满足堆的性质，右节点左旋，所以需要保存进入的是左子树还是右子树方便旋转，而且注意最低层（叶子节点）更新后，其祖先节点可能也不满足堆，所以也需要旋转，根节点节点个数也可能变化了，注意更新，旋转请看平衡二叉树的旋转http://blog.csdn.net/wsnbb123456789/article/details/53192406。

void Rotate ( Node * &o, int k ) { Node * p = o->ch[k^1]; o->ch[k^1] = p->ch[k]; p->ch[k] = o; o->maintain ( ); p->maintain ( ); o = p; } void insert ( Node * &T, int x ) { if ( T == null ) { T = new Node ( ); T->x = x; T->cnt = 1; T->r = rand ( ); T->ch[0] = T->ch[1] = null; return ; } int d = T->cmp ( x ); if ( d == -1 ) d = 0; insert ( T->ch[d], x ); if ( T->r < T->ch[d]->r ) Rotate ( T, d^1 ); T->maintain ( ); }删除就比较简单一些，如果只有左子树或右子树直接用其替代就行，都存在就旋转使其变成一个子树或为叶结点，旋转时考虑的是删除此节点后还是要满足Treap的性质，而旋转是不会改变性质1的，要保持性质2就看左节点和右节点哪个优先级高，哪个就作为根节点（大顶堆是如此），按此依据进行旋转即可。

void remove ( Node * &T, int x ) { if ( T == null ) return ; int d = T->cmp ( x ); if ( d == -1 ) { if ( T->ch[0] != null && T->ch[1] != null ) { int d2 = T->ch[0]->r < T->ch[1]->r ? 0 : 1; Rotate ( T, d2 ); remove ( T->ch[d2], x ); } else { Node * p = T; if ( T->ch[0] != null ) T = T->ch[0]; else T = T->ch[1]; delete p; return ; } } else remove ( T->ch[d], x ); T->maintain ( ); } HYSBZ 1503 郁闷的出纳员 此题难点在于小于min值节点的删除，可以旋转使根节点大于等于min，而左子树小于min时即可直接删除左子树就行。

至于全部节点加一个数或减一个数可以加变量维护，或者直接变化min，保存一个min的变化值。

#include <cstdio> #include <cstring> #include <string> #include <algorithm> #include <cmath> #include <cstdlib> #include <utility> #include <map> #include <set> #include <queue> #include <vector> #include <iostream> #include <stack> using namespace std; #define INF 0x3f3f3f3f #define eps 1e-6 #define CLR( a, v ) memset ( a, v, sizeof ( a ) ) #define LL long long #define DBUG printf ( "here!!!" ) #define rep( i, a, b ) for ( int i = ( a ); i < ( b ); i ++ ) #define PB push_back #define ULL unsigned long long #define PI acos ( -1.0 ) #define lson l, m, rt << 1 #define rson m+1, r, rt << 1 | 1 #define lowbit( x ) ( ( x )&( -x ) ) #define CASE int Test; scanf ( "%d", &Test ); for ( int cas = 1; cas <= Test; cas ++ ) #define ALL( x ) x.begin ( ), x.end ( ) #define INS( x ) x, x.begin ( ) typedef pair < int, int > Pii; typedef pair < double, double > Pdd; typedef set < int > Set; const int maxn = 105; int read_int ( ) { int res = 0; int ch; while ( ( ch = getchar ( ) ) && ! ( ch >= '0' && ch <= '9' ) ) { if ( ch == -1 ) return -1; } while ( ch >= '0' && ch <= '9' ) { res = res*10+( ch-'0' ); ch = getchar ( ); } return res; } struct Node { int x, r, cnt; struct Node * ch[2]; void maintain ( ) { cnt = 1; if ( ch[0] != NULL ) cnt += ch[0]->cnt; if ( ch[1] != NULL ) cnt += ch[1]->cnt; } }*root; void Rotate ( Node * &o, int k ) { Node * p = o->ch[k^1]; o->ch[k^1] = p->ch[k]; p->ch[k] = o; o->maintain ( ); p->maintain ( ); o = p; } void insert ( Node * &T, int x ) { if ( T == NULL ) { T = new Node ( ); T->x = x; T->r = rand ( ); T->cnt = 1; T->ch[0] = T->ch[1] = NULL; return ; } int k = T->x > x ? 0 : 1; insert ( T->ch[k], x ); if ( T->r < T->ch[k]->r ) Rotate ( T, k^1 ); T->maintain ( ); } void free ( Node * &T ) { if ( T == NULL ) return ; if ( T->ch[0] != NULL ) free ( T->ch[0] ); if ( T->ch[1] != NULL ) free ( T->ch[1] ); delete T; T = NULL; } int ans; void deleteMin ( Node * &T, int p ) { if ( T == NULL ) return ; if ( T->x >= p ) deleteMin ( T->ch[0], p ); else { //将比x大的数旋转至根节点 while ( T->x < p && T->ch[1] != NULL ) Rotate ( T, 0 ); if ( T->x < p ) { ans += T->cnt; free ( T ); delete T; T = NULL; return ; } else deleteMin ( T->ch[0], p ); } T->maintain ( ); } int Kth_rank ( Node * T, int k ) { if ( T == NULL ) return -1; if ( T->cnt < k ) return -1; int x = ( T->ch[1] != NULL ? T->ch[1]->cnt : 0 )+1; if ( x == k ) return T->x; if ( x-1 >= k ) return Kth_rank ( T->ch[1], k ); return Kth_rank ( T->ch[0], k-x ); } void solve ( ) { int n, mn, x, tmp = 0; char op[5]; ans = 0; scanf ( "%d%d", &n, &mn ); root = NULL; while ( n -- ) { scanf ( "%s%d", op, &x ); if ( op[0] == 'I' ) { if ( x+tmp >= mn ) insert ( root, x+tmp ); } else if ( op[0] == 'A' || op[0] == 'S' ) { if ( op[0] == 'S' ) x = -x; mn -= x; tmp -= x; if ( op[0] == 'S' ) deleteMin ( root, mn ); } else { int res = Kth_rank ( root, x ); if ( res != -1 ) res -= tmp; printf ( "%d\n", res ); } } printf ( "%d\n", ans ); } int main ( ) { solve ( ); return 0; }