fhq treap

结构

1
2
3
4
5
6
7
8
9
10
struct node{
    int l,r;
    int val, key;
    int Size;
    #define l(u) fhq[u].l
    #define r(u) fhq[u].r
    #define Size(u) fhq[u].Size
    #define v(u) fhq[u].val
    #define key(u) fhq[u].key
}fhq[N];

储存左右儿子，值，索引（用于平衡），树的大小。

基本操作

新建

1
2
3
4
5
6
int newnode(int val) {
    fhq[++cnt].val = val;
    fhq[cnt].key = rnd();
    fhq[cnt].Size = 1;
    return cnt;
}

更新

1
2
3
void update(int u) {
    Size(u) = Size(l(u)) + Size(r(u)) + 1;
}

分裂

按值分裂，把树拆成两棵，一棵全部小于等于给定值，另一棵大于给定值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void split(int u,int val, int &x, int &y) {
    if (!u) x = y = 0;
    //一棵全部小于等于给定值，另一棵全部大于给定值
    else {
        if (v(u) <= val) {
            x = u;
            split(r(u),val,r(u),y);  
        }else {
            y = u;
            split(l(u), val, x , l(u));
        }
        update(u);
    }
}

合并

1
2
3
4
5
6
7
8
9
10
11
12
13
int merge(int x,int y) {
    if (!x || !y) return x + y;
    if (key(x) > key(y)) {//x的值大于y
        r(x) = merge(r(x),y);//x的右子树就是y
        update(x);
        return x;
    }
    else {
        l(y) = merge(x,l(y));//y的左子树是x
        update(y);
        return y;
    }
}

插入

按值分裂，合并后达到插入效果

1
2
3
4
void Insert(int val) {//插入
    split(root,val,x,y);//按值val把树分成x和y
    root = merge(merge(x,newnode(val)),y);//创建一个新结点，再把xy合并
}

删除

设值为vv，按vv把树分裂成xx（左）和zz（右）。

按v−1v-1把xx分成xx（左）和yy（右）。

此时yy树上所有值都是vv，让yy为yy的左右子树合并后的树，达到删除效果。

最后合并xyzxyz。

1
2
3
4
5
6
7
void del(int val) {//删除
    split(root,val,x,z);//按val把树分裂成x和z
    split(x,val-1,x,y);//按val-1把x树分成x和y
    y = merge(l(y), r(y));//此时y树上所有值都是val；
    //删除y，即让y为y的左右子树的并
    root = merge(merge(x,y),z);//最后合并xyz
}

查询值的排名

若查询值为vv：

按v−1v-1分裂成xx和yy。

xx的大小加上11就是vv的排名。

合并xyxy。

1
2
3
4
5
void getrank(int val) {//查询值的排名
    split(root,val-1,x,y);//按val-1分裂成x和y
    printf("%lld\n",Size(x) + 1);//x的大小+ 1就是val的排名
    root = merge(x,y);//合并xy
}

查询排名的值

遍历寻找。

如果左子树大小+1+1为rankrank，说明已经找到。

如果左子树大小大于rankrank，说明在左子树中。

否则在右子树中。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void getnum(int rank) {//查询排名的值
    int u = root;
    while (u) {
        if (Size(l(u)) + 1 == rank) break; //如果左子树大小+ 1 为rank，说明已找到
        else if (Size(l(u)) >= rank) //如果左子树大小大于等于rank
        //说明要找的在左子树中
            u = l(u);
        else {
            rank -= Size(l(u)) + 1;
            u = r(u);
        }//否则在右子树中
    }
    printf("%lld\n",v(u));
}

前驱

查询vv:

按v−1v-1分裂成xx，yy。则xx里面最右的数就是vv前驱。

1
2
3
4
5
6
7
8
void pre(int val) {//前驱
    split(root,val-1,x,y);//按val-1分裂成x和y
    //x里面最右的数就是val前驱
    int u = x;
    while (r(u)) u = r(u);
    printf("%lld\n",v(u));
    root = merge(x,y);
}

后继

查询vv:

按vv分裂成xx，yy。则yy里面最左的数就是vv的后继。

1
2
3
4
5
6
7
8
void nxt(int val) {
    split(root,val,x,y);//按val分裂成x和y
    //y里面最左的数就是val后继
    int u = y;
    while (l(u)) u = l(u);
    printf("%lld\n",v(u));
    root = merge(x,y);
}

模板题：

https://www.luogu.com.cn/problem/P3369

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
123
124
125
126
127
128
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <ctime>
#include <random>
#define int long long
using namespace std;

const int N = 1e5 + 8;

struct node{
    int l,r;
    int val, key;
    int Size;
    #define l(u) fhq[u].l
    #define r(u) fhq[u].r
    #define Size(u) fhq[u].Size
    #define v(u) fhq[u].val
    #define key(u) fhq[u].key
}fhq[N];

int cnt,root;

mt19937 rnd(23311113);

int newnode(int val) {
    fhq[++cnt].val = val;
    fhq[cnt].key = rnd();
    fhq[cnt].Size = 1;
    return cnt;
}

void update(int u) {
    Size(u) = Size(l(u)) + Size(r(u)) + 1;
}

void split(int u,int val, int &x, int &y) {
    if (!u) x = y = 0;
    //一棵全部小于等于给定值，另一棵全部大于给定值
    else {
        if (v(u) <= val) {
            x = u;
            split(r(u),val,r(u),y);  
        }else {
            y = u;
            split(l(u), val, x , l(u));
        }
        update(u);
    }
}

int merge(int x,int y) {
    if (!x || !y) return x + y;
    if (key(x) > key(y)) {//x的值大于y
        r(x) = merge(r(x),y);//x的右子树就是y
        update(x);
        return x;
    }
    else {
        l(y) = merge(x,l(y));//y的左子树是x
        update(y);
        return y;
    }
}

int x,y,z;

void Insert(int val) {//插入
    split(root,val,x,y);//按值val把树分成x和y
    root = merge(merge(x,newnode(val)),y);//创建一个新结点，再把xy合并
}
void del(int val) {//删除
    split(root,val,x,z);//按val把树分裂成x和z
    split(x,val-1,x,y);//按val-1把x树分成x和y
    y = merge(l(y), r(y));//此时y树上所有值都是val；
    //删除y，即让y为y的左右子树的并
    root = merge(merge(x,y),z);//最后合并xyz
}
void getrank(int val) {//查询值的排名
    split(root,val-1,x,y);//按val-1分裂成x和y
    printf("%lld\n",Size(x) + 1);//x的大小+ 1就是val的排名
    root = merge(x,y);//合并xy
}
void getnum(int rank) {//查询排名的值
    int u = root;
    while (u) {
        if (Size(l(u)) + 1 == rank) break; //如果左子树大小+ 1 为rank，说明已找到
        else if (Size(l(u)) >= rank) //如果左子树大小大于等于rank
        //说明要找的在左子树中
            u = l(u);
        else {
            rank -= Size(l(u)) + 1;
            u = r(u);
        }//否则在右子树中
    }
    printf("%lld\n",v(u));
}
void pre(int val) {//前驱
    split(root,val-1,x,y);//按val-1分裂成x和y
    //x里面最右的数就是val前驱
    int u = x;
    while (r(u)) u = r(u);
    printf("%lld\n",v(u));
    root = merge(x,y);
}
void nxt(int val) {
    split(root,val,x,y);//按val分裂成x和y
    //y里面最左的数就是val后继
    int u = y;
    while (l(u)) u = l(u);
    printf("%lld\n",v(u));
    root = merge(x,y);
}

signed main () {
    int n;
    cin >> n;
    for (int i =1; i <= n; i ++ ) { 
        int op,x;
        scanf("%lld%lld",&op,&x);
        if(op == 1)  Insert(x);
        else if (op == 2) del(x);
        else if (op == 3) getrank(x);
        else if (op == 4) getnum(x);
        else if (op == 5) pre(x);
        else nxt(x);
    }
}

文艺平衡树

区间上操作，实现方式类似线段树

https://www.luogu.com.cn/problem/P3391

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
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <ctime>
#include <random>
#define int long long
using namespace std;

const int N = 1e5 + 8;

struct node{
    int l,r;
    int val, key;
    int Size;
    bool flag;
    #define l(u) fhq[u].l
    #define r(u) fhq[u].r
    #define Size(u) fhq[u].Size
    #define v(u) fhq[u].val
    #define key(u) fhq[u].key
    #define flag(u) fhq[u].flag
}fhq[N];

int cnt,root;

mt19937 rnd(23311113);

int newnode(int val) {
    fhq[++cnt].val = val;
    fhq[cnt].key = rnd();
    fhq[cnt].Size = 1;
    return cnt;
}
void pushdown(int u) {
    swap(l(u),r(u));
    flag(l(u)) ^= 1;
    flag(r(u)) ^= 1;
    flag(u) ^= 1;
}
void update(int u) {
    Size(u) = Size(l(u)) + Size(r(u)) + 1;
}

void split(int u,int siz, int &x,int &y) {
    if (!u) x = y = 0;
    else {
        if (flag(u)) pushdown(u);
        if (Size(l(u)) < siz) {
            x = u;
            split(r(u),siz - Size(l(u))-1,r(u),y);
        }else {
            y = u;
            split(l(u), siz,x, l(u));
        }
        update(u);
    }
}

int merge(int x,int y) {
    if (!x || !y) return x + y;
    if (key(x) < key(y)) {
        if (flag(x)) pushdown(x);
        r(x) = merge(r(x),y);
        update(x);
        return x;
    }else {
        if (flag(y)) pushdown(y);
        l(y) = merge(x,l(y));
        update(y);
        return y;
    }
}

int x,y,z;

void Reverse(int l,int r) {
    split(root,l-1,x,y);
    split(y,r-l+1,y,z);
    flag(y) ^= 1;
    root = merge(merge(x,y),z);
}

void output(int u) {
    if (!u) return ;
    if (flag(u) ) pushdown(u);
    output(l(u));
    cout << v(u) << ' ';
    output(r(u));
}

signed main () {
    int n,m;
    cin >> n >> m;
    for (int i = 1; i <= n; i ++ ) 
        root = merge(root,newnode(i));
    while (m--) { 
        int l,r;
        cin >> l >> r;Reverse(l,r);
    }
    output(root);
}