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

Home

文艺平衡树

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;
}