Splay 实现区间翻转(文艺平衡树)

思路

之前我们讲到了用 Splay 写普通平衡树,这次我们将用 Splay 来完成区间操作。

之前的 Splay 是按照权值排序,而这里的 Splay 则是要按照编号排序。

不难想到,整棵树的编号第 k 大点即数列中的第 k 个,整棵树的中序遍历即被维护的数列。


假设我们要翻转区间[l, r],那么我们先把l - 1旋转到根节点,再把r + 1旋转到根节点的右孩子。那么r + 1的左子树即区间[l, r]。翻转该区间只需要把该区间内的每个节点的左右子树交换即可。

参考线段树的 lazytag,我们也使用一个类似于懒标记的方法,保证复杂度为O(log n)

1.png

基本操作

和普通平衡树一样。

1
2
3
4
5
6
7
8
9
10
void update(int x) {
e[x].sum = e[e[x].ch[0]].sum + e[e[x].ch[1]].sum + e[x].cnt;
}
int identify(int x) {
return e[e[x].father].ch[1] == x;
}
void connect(int u, int f, int son) {
e[u].father = f;
e[f].ch[son] = u;
}

懒标记下放

把当前节点的懒标记传给两个孩子,同时交换两个孩子的指针。

1
2
3
4
5
6
7
8
void pushdown(int x) {
if (e[x].tag) {
swap(e[x].ch[0], e[x].ch[1]);
e[e[x].ch[0]].tag ^= 1;
e[e[x].ch[1]].tag ^= 1;
e[x].tag = 0;
}
}

上旋 & Splay

和普通平衡树的操作相同,只不过需要先pushdown()改变了的节点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void rotate(int x) {
int f = e[x].father, ff = e[f].father;
pushdown(f), pushdown(x);
int fson = identify(x), ffson = identify(f);
int y = e[x].ch[fson ^ 1];
connect(y, f, fson);
connect(f, x, fson ^ 1);
connect(x, ff, ffson);
update(f);
update(x);
}
void splay(int at, int to) {
to = e[to].father;
while (e[at].father != to) {
int up = e[at].father;
pushdown(up), pushdown(at);
if (e[up].father == to) rotate(at);
else if (identify(at) == identify(up)) rotate(up), rotate(at);
else rotate(at), rotate(at);
}
}

查找

与普通平衡树的查找第 k 大相同。

由于只会在reverse操作中被调用所以没有 splay 到根。

1
2
3
4
5
6
7
8
9
10
int find(int x) {
int u = root;
while (u) {
pushdown(u);
int mincost = e[e[u].ch[0]].sum + e[u].cnt;
if (e[e[u].ch[0]].sum < x && x <= mincost) return u;
if (x < mincost) u = e[u].ch[0];
else x -= mincost, u = e[u].ch[1];
}
}

建树

setroot()操作用于在外部定义根节点。

build()操作类似于线段树,直接建树比写insert()操作插入节点要快。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void setroot(int x) {
root = x;
}
void build(int l, int r, int f) {
if (l > r) return;
int m = (l + r) >> 1;
e[m].val = m, e[m].father = f;
e[m].cnt = e[m].sum = 1;
e[m].ch[0] = e[m].ch[1] = 0;
if (m < f) e[f].ch[0] = m;
else e[f].ch[1] = m;
build(l, m - 1, m);
build(m + 1, r, m);
update(m);
}

翻转

参照之前的图。需要注意的是这样的写法需要下文初始化的配合

1
2
3
4
5
6
void reverse(int l, int r) {
int x = find(l - 1), y = find(r + 1);
splay(x, root);
splay(y, e[x].ch[1]);
e[e[y].ch[0]].tag ^= 1;
}

初始化

我们先使用build()操作建树。其中2 ~ n + 1节点表示数列的第1 ~ n个。

插入1n + 2节点是为了保证被查找的树必定在区间内简化代码量。

1
2
s.setroot((n + 3) >> 1);
s.build(1, n + 2, 0);

代码

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
// ==============================
// author: memset0
// website: https://memset0.cn
// ==============================
#include <bits/stdc++.h>
#define ll long long
using namespace std;

int read() {
int x = 0; bool m = 0; char c = getchar();
while (!isdigit(c) && c != '-') c = getchar();
if (c == '-') m = 1, c = getchar();
while (isdigit(c)) x = x * 10 + c - '0', c = getchar();
if (m) return -x; else return x;
}

const int maxn = 100010;
int n, m, l, r;

struct Splay {
#define root (e[0].ch[1])
struct node {
int val, sum, cnt, tag;
int father, ch[2];
} e[maxn];
void setroot(int x) {
root = x;
}
void update(int x) {
e[x].sum = e[e[x].ch[0]].sum + e[e[x].ch[1]].sum + e[x].cnt;
}
int identify(int x) {
return e[e[x].father].ch[1] == x;
}
void connect(int u, int f, int son) {
e[u].father = f;
e[f].ch[son] = u;
}
void pushdown(int x) {
if (e[x].tag) {
swap(e[x].ch[0], e[x].ch[1]);
e[e[x].ch[0]].tag ^= 1;
e[e[x].ch[1]].tag ^= 1;
e[x].tag = 0;
}
}
void rotate(int x) {
int f = e[x].father, ff = e[f].father;
pushdown(f), pushdown(x);
int fson = identify(x), ffson = identify(f);
int y = e[x].ch[fson ^ 1];
connect(y, f, fson);
connect(f, x, fson ^ 1);
connect(x, ff, ffson);
update(f);
update(x);
}
void splay(int at, int to) {
to = e[to].father;
while (e[at].father != to) {
int up = e[at].father;
pushdown(up), pushdown(at);
if (e[up].father == to) rotate(at);
else if (identify(at) == identify(up)) rotate(up), rotate(at);
else rotate(at), rotate(at);
}
}
int find(int x) {
int u = root;
while (u) {
pushdown(u);
int mincost = e[e[u].ch[0]].sum + e[u].cnt;
if (e[e[u].ch[0]].sum < x && x <= mincost) return u;
if (x < mincost) u = e[u].ch[0];
else x -= mincost, u = e[u].ch[1];
}
}
void build(int l, int r, int f) {
if (l > r) return;
int m = (l + r) >> 1;
e[m].val = m, e[m].father = f;
e[m].cnt = e[m].sum = 1;
e[m].ch[0] = e[m].ch[1] = 0;
if (m < f) e[f].ch[0] = m;
else e[f].ch[1] = m;
if (l == r) return;
build(l, m - 1, m);
build(m + 1, r, m);
update(m);
}
void reverse(int l, int r) {
int x = find(l - 1), y = find(r + 1);
splay(x, root);
splay(y, e[x].ch[1]);
e[e[y].ch[0]].tag ^= 1;
}
#undef root
} s;

int main() {

n = read(), m = read();
s.setroot((n + 3) >> 1);
s.build(1, n + 2, 0);
while (m--) {
l = read(), r = read();
s.reverse(l + 1, r + 1);
}
for (int i = 1; i <= n; i++)
printf("%d ", s.find(i + 1) - 1);
putchar('\n');

return 0;
}

备注 & 参考资料

参考资料:

代码提交:

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×