Bzoj 3223(Treap)

BZOJ 3223
平衡树模板题,处理区间问题,本题用下标来做$key$,区间翻转直接交换两棵子树,因为$key$按中序遍历有序。而交换两棵子树虽然破坏了排序二叉树的性质,但是并不影响解题,只需要知道当前节点在区间的某个位置就行了

非旋转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
#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;
int n;
struct Treap *null, *root, *pit;
struct Treap {
int val, key, s, rev;
Treap *lc, *rc;
void init(int key) {rev = 0, this->key = key, val = rand(), s = 1, lc = rc= null;}
void maintain() {s = lc->s + rc->s + 1;}
}pool[MAXN];
Treap* newNode(int key) {
pit->init(key);
return pit++;
}
void pushdown(Treap *&o) {
if (o->rev) {
o->lc->rev ^= 1, o->rc->rev ^= 1;
swap(o->lc, o->rc);
o->rev = 0;
}
}
Treap* merge(Treap *a, Treap *b) {
if (a == null) return b;
if (b == null) return a;
pushdown(a), pushdown(b);
if (a->val < b->val) {
a->rc = merge(a->rc, b), a->maintain();
return a;
} else {
b->lc = merge(a, b->lc), b->maintain();
return b;
}
}
void split(Treap *o, int k, Treap *&x, Treap *&y) {
if (o == null) x = y = null; else {
pushdown(o);
if (k <= o->lc->s) {
y = o, split(o->lc, k, x, o->lc);
} else x = o, split(o->rc, k - o->lc->s - 1, o->rc, y);
o->maintain();
}
}
void insert(int x) {
root = merge(root, newNode(x));//由于插入是从小到大的,所以直接合并
}
void reverse(int l, int r) {
Treap *a, *b;
split(root, r, a, b);
Treap *c, *d;
split(a, l - 1, c, d);
d->rev = 1;
a = merge(c, d), root = merge(a, b);
}
void print(Treap *o) {
if (o == null) return ;
pushdown(o);
print(o->lc);
printf("%d ", o->key);
print(o->rc);
}
void initTreap() {
srand(19260817);
pit = pool;
null = newNode(0), null->s = 0;
root = null;
}
void clean() {
}
void solve() {
clean();
int Q;
scanf("%d%d", &n, &Q);
initTreap();
for (int i = 1; i <= n; i++) insert(i);
while (Q--) {
int l, r;
scanf("%d%d", &l, &r);
reverse(l, r);
}
print(root);
}
int main() {
solve();
return 0;
}

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