= Vain学习(C/C++ acm算法 python Linux Golang)的个人网站 =

文艺平衡树

Posted on

传送门:文艺平衡树
首先要阐述一点,Fhq Treap的按大小分裂是支持区间操作的,而按值分裂是不支持区间操作的。
Fhq Treap的分裂方式:

  • 按权值分裂
  • 按大小分裂

按权值分裂:

根据插入点的权值,将树按w为边界,分裂为两颗树,一颗树的权值大于w,一棵树的权值小于等于w,这样再把新节点合并进去,就可以维护树的平衡

按大小分裂:

根据插入点的节点大小,将树按big为边界,分裂为两颗树,一颗树的节点大小大于big,一棵树的节点大小小于等于big,这样再把新节点合并进去,不仅可以维护树的平衡,还支持区间操作

为什么按大小分裂会支持区间操作:

首先,新开的每一个节点,都可以用节点数量,代表区间中的一个端点,呢么我们如果修改区间,呢么我们只需要修改平衡树中节点数量在我们要修改的区间内即可,然后合并成新的平衡树即可,一颗平衡树的节点对应数量是一样的,我们只需要改变节点对应的值即可

该题思路:

利用支持区间修改的Fhq Treap,我们利用懒惰标记,对区间进行修改,交换当前区间的左右子树,从而达到颠倒一个区间

:随机库函数,好多版本的C++不支持,所以就自己写一个叭

参考代码:

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
#include <cstdio>
#include <algorithm>
#include <vector>
#include <iostream>
#include <map>
#include <queue>
#include <cstring>
#include <string>
#include <cstdlib>
#include <cmath>
#include <set>
using namespace std;
const int inf = (1 << 30);
typedef long long ll;
const int base = 131;
const int maxn = 1e5 + 5;
//vector<ll> vec;
//ll n, sum[maxn * 10], c[maxn * 10], a[maxn];
//vector<int> vec;
int su = 1;
int rand()
{
su = (su * base) % 1000007;
return su;
}
int cnt, rt;
struct node
{
int ls, rs, w;
int key, sizx;
int lazy;
} tr[maxn*50];
int newnode(int w)
{
tr[++cnt].w = w, tr[cnt].sizx = 1;
tr[cnt].lazy=0;
tr[cnt].key = rand();
return cnt;
}
void pushup(int now)
{
tr[now].sizx = tr[tr[now].ls].sizx + tr[tr[now].rs].sizx + 1;
}
void pushdown(int now)
{
if (tr[now].lazy)
{
swap(tr[now].ls, tr[now].rs);
tr[tr[now].ls].lazy ^= 1;
tr[tr[now].rs].lazy ^= 1;
tr[now].lazy = 0;
}
}
void split(int now, int big, int &x, int &y)
{
if (!now)
x = y = 0;
else
{
pushdown(now);
if (tr[tr[now].ls].sizx < big)
x = now, split(tr[now].rs, big - tr[tr[now].ls].sizx - 1, tr[now].rs, y);
else
y = now, split(tr[now].ls, big, x, tr[now].ls);
pushup(now);
}
}
int merge(int x, int y)
{
if (!x || !y)
return x + y;
if (tr[x].key > tr[y].key)
{
pushdown(x);
tr[x].rs = merge(tr[x].rs, y);
pushup(x);
return x;
}
else
{
pushdown(y);
tr[y].ls = merge(x, tr[y].ls);
pushup(y);
return y;
}
}
void reverse(int l, int r)
{
int x, y, z;
split(rt, l-1, x, y);
split(y, r - l + 1, y, z);
tr[y].lazy ^= 1;
rt = merge(merge(x, y), z);
}
void dfs(int now)
{
if (!now)
return;
pushdown(now);
dfs(tr[now].ls);
cout << tr[now].w << ' ';
dfs(tr[now].rs);
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; i++)
{
rt = merge(rt, newnode(i));
}
while (m--)
{
int ql, qr;
cin >> ql >> qr;
reverse(ql, qr);
}
dfs(rt);
cout<<endl;
}