非旋转Treap 学习笔记

模板及讲解
非旋转Treap:
Treap=Tree+heap,即键值$key$(满足排序二叉树性质(左小右大),并且按照中序遍历有序),附加值$val$(满足堆性质(孩子都比父节点小))
核心操作$O(nlogn)$:

  • $newNode(x)$ 新建一个以$x$为权值的点
  • $merge(a, b)$ 把$a$树和$b$树合并,必须满足$\forall key_a < \forall key_b$
  • $split_v(a,v,x,y)$把$a$树按权值$v$分成$x,y$两棵树,一棵树小于等于$v$,一棵树大于$v$
  • $split_k(a,v,x,y)$把$a$树按前$k$个分配成$x,y$两棵树

能够实现的操作$O(nlogn)$:

  • $rank(x)$ 查询$x$的排名
  • $kth(x)$ 查询第$x$大的数
  • $pre(x)$ 查询$x$的前驱
  • $succ(x)$ 查询$x$的后继
  • $insert(x)$ 插入一个数权值为$x$
  • $del(x)$ 删除一个权值为$x$的数

具体可以看相关代码
写时注意:
1 不要忘了srand(19260817)
2 $split$里$x, y$用*&
3 主程序记得加$initTreap()$
4 $merge$前面记得加赋值

可持久化Treap:
暂略

常见题型
1、直接使用操作完成
Q: 求第$k$大\求$x$的排名……
解: 直接套模板。
例题: bzoj3224
2、操作区间
Q: 翻转某个区间
解: 非旋Treap处理区间。
例题: bzoj3223

相关代码
bzoj3224非旋转Treap模板:包括基本操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
using namespace std;
const int MAXN = 100000 + 5;
struct Treap *null, *pit, *root;//自建的null节点,内存池指针
struct Treap {
int key, val, s;//键值(满足排序二叉树性质),附加值(满足堆性质),以本节点为根的子树大小
Treap *lc, *rc;//Treap 左右结点
Treap() {};
void init(int key) {this->key = key, val = rand(), lc = rc = null, s = 1;}//初始化
void maintain() {s = lc->s + rc->s + 1;}//更新,维护以本节点为根的子树大小
}pool[MAXN];//内存池
Treap* newNode(int key) {
pit->init(key);
return pit++;
}
Treap* merge(Treap *a, Treap *b) {//合并两棵Treap,所有key(a)<key(b)才能合并,为了满足排序二叉树性质
if (a == null) return b;
if (b == null) return a;
if (a->val < b->val) {
a->rc = merge(a->rc, b), a->maintain();
//a小自然a要在b的上面,满足堆性质
return a;
}
if (a->val >= b->val) {
b->lc = merge(a, b->lc), b->maintain();
//a大自然a要在b的下面,满足堆性质
return b;
}
}
void split_v(Treap *o, int v, Treap *&x, Treap *&y) {//用权值分开一棵Treap,分开的第一棵根为x,第二棵根为y。x,y可以称为左右子树“下一个”位置,也就是如果还有满足左边的,就放在x或者y的位置
if (o == null) x = y = null; else {
if (o->key <= v) {
x = o, split_v(o->rc, v, o->rc, y);//x = o说明o左边全部放进x,递归右子树
} else y = o, split_v(o->lc, v, x, o->lc);
o->maintain();
}
}
void split_k(Treap *o, int k, Treap *&x, Treap *&y) {//按前k个分配分开一棵Treap,分开的第一棵根为x,第二棵根为y。x,y可以称为左右子树“下一个”位置,也就是如果还有满足左边的,就放在x或者y的位置
if (o == null) x = y = null; else {
if (k <= o->lc->s) {
y = o, split_k(o->lc, k, x, o->lc);//y = o说明o右边全部放进y,递归左子树
} else x = o, split_k(o->rc, k - o->lc->s - 1, o->rc, y);
o->maintain();
}
}
void insert(int v) {//插入一个数
Treap *a, *b;
split_v(root, v, a, b);
root = merge(merge(a, newNode(v)), b);
}
void del(int v) {//删除一个数
Treap *a, *b;
split_v(root, v, a, b);
Treap *c, *d;
split_v(a, v - 1, c, d);
d = merge(d->lc, d->rc);
a = merge(c, d), root = merge(a, b);
}
int kth(int k) {//查询排名为k的数
Treap *a, *b;
split_k(root, k - 1, a, b);
Treap *c, *d;
split_k(b, 1, c, d);
int ret = c->key;
b = merge(c, d), root = merge(a, b);
return ret;
}
int rk(int x) {//查询x的排名
Treap *a, *b;
split_v(root, x - 1, a, b);
int ret = a->s + 1;
root = merge(a, b);
return ret;
}
int pre(int x) {//求x的前驱
Treap *a, *b;
split_v(root, x - 1, a, b);
Treap *c, *d;
split_k(a, a->s - 1, c, d);
int ret = d->key;
a = merge(c, d), root = merge(a, b);
return ret;
}
int succ(int x) {//求x的后继
Treap *a, *b;
split_v(root, x, a, b);
Treap *c, *d;
split_k(b, 1, c, d);
int ret = c->key;
b = merge(c, d), root = merge(a, b);
return ret;
}
void initTreap() {
srand(19260827);//置随机数种子
pit = pool;//指针指向内存池
null = newNode(0), null->s = 0;//初始化自建的null节点
root = null;//初始化树根
}
void clean() {}
void solve() {
clean();
initTreap();
int Q;
scanf("%d", &Q);
while (Q--) {
int opt, x;
scanf("%d%d", &opt, &x);
switch (opt) {
case 1: insert(x); break;
case 2: del(x); break;
case 3: printf("%d\n", rk(x)); break;
case 4: printf("%d\n", kth(x)); break;
case 5: printf("%d\n", pre(x)); break;
case 6: printf("%d\n", succ(x)); break;
}
}
}
int main() {
solve();
return 0;
}

------ 本文结束 ------