植树节栽树计画(三) fhqtreap维护区间

fhqtreap维护区间

事实上,刚才我们做的类似值域线段树;而现在我们要做的是一般线段树的工作。

我们先来试着完成一项工作:luogu3391文艺平衡树。我们要求要维护区间翻转。

这个东西看上去非常困难,但是在fhqtreap面前,它的这样工作的:

我们用一个fhqtreap维护区间。注意,每一个点代表的不是权值,而是这个点本身。然后想要将[l, r]翻转,我们直接split出[l, r]这棵树。我们发现一个性质:翻转[l, r]等价于将这棵树左右子树交换。所以我们直接打个要翻转的标记,之后再慢慢下传。然后打好标记再merge回去。

1
2
3
4
5
6
inline void push_down(int h) {
if(h && tree[h].rev) {
tree[ls].rev ^= 1; tree[rs].rev ^= 1;
tree[h].rev = 0; swap(ls, rs);
}
}

注意一个问题。我们之前的分割,都是以权值为基准进行分割,这样分割对于值域有更大的效率。但是这里如果按照值域分割会使区间GG,所以,我们以元素个数为基准分割。

1
2
3
4
5
6
7
8
inline void split(int h, int& a, int& b, int k) {
if(!h) {a = b = 0; return;}
push_down(h);
if(k <= tree[ls].siz)
b = h, split(ls, a, ls, k);
else a = h, split(rs, rs, b, k - tree[ls].siz - 1);
push_up(h);
}

然后就可以reverse了:

1
2
3
4
5
6
7
8
inline void reverse(int l, int r) {
int a, b, c, d;
split(rt, a, b, r);
split(a, c, d, l - 1);
tree[d].rev ^= 1;
merge(a, c, d);
merge(rt, a, b);
}

意思也很简单,做法简单粗暴。先split成两部分,然后再把区间split出来,最后再merge回去。

那么文艺平衡树就可以AC了:

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
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstdlib>
#include <ctime>
#include <cstring>
#include <climits>

using namespace std;

#define N 100003
#define ls tree[h].son[0]
#define rs tree[h].son[1]

struct node{
int val, rnd, son[2], siz, rev;
}tree[N];

int rt;

inline void push_up(int h) {
tree[h].siz = tree[ls].siz + tree[rs].siz + 1;
}

inline void push_down(int h) {
if(h && tree[h].rev) {
tree[ls].rev ^= 1; tree[rs].rev ^= 1;
tree[h].rev = 0; swap(ls, rs);
}
}

inline void make_heap(int h, int x) {
tree[h].rnd = rand();
tree[h].val = x, tree[h].siz = 1;
}

inline void merge(int& h, int a, int b) {
if(!a || !b) {h = a + b; return; }
push_down(a); push_down(b); //注意这里push_down两颗树
if(tree[a].rnd < tree[b].rnd)
h = a, merge(rs, rs, b);
else h = b, merge(ls, a, ls);
push_up(h);
}

inline void split(int h, int& a, int& b, int k) {
if(!h) {a = b = 0; return;}
push_down(h);
if(k <= tree[ls].siz)
b = h, split(ls, a, ls, k);
else a = h, split(rs, rs, b, k - tree[ls].siz - 1);
push_up(h);
}

inline void reverse(int l, int r) {
int a, b, c, d;
split(rt, a, b, r);
split(a, c, d, l - 1);
tree[d].rev ^= 1;
merge(a, c, d);
merge(rt, a, b);
}

inline void go(int h) {
if(tree[h].rev) push_down(h);
if(ls) go(ls);
printf("%d ", tree[h].val);
if(rs) go(rs);
}

int n, m;

int main() {
srand(19260817);
cin>>n>>m;
rt = 0; tree[0].rnd = tree[0].val = INT_MAX;
int l, r;
for(int i = 1; i <= n; ++i) make_heap(i, i), merge(rt, rt, i);
for(int i = 1; i <= m; ++i) {
cin>>l>>r;
reverse(l, r);
}
go(rt);
return 0;
}
Share