首页 > 代码库 > 好久不见的博客咯！——没有可持久化的可持久化treap

好久不见的博客咯！——没有可持久化的可持久化treap

2024-07-06 21:52:41   227人阅读

每每想要去了解可持久化treap这个好写好调的东东，然后就发现网上只有一个人的——SymenYang的！在此我必须得把他批判一番——写方法不贴代码是什么心态！而且写出来的是有问题的呀！害人不浅！

好吧说正经事，这个版本的treap名叫可持久化treap却没有可持久化，而是借鉴了可持久化treap中的一些写法。貌似可持久化之后反而难写难调。。。在这个版本的treap中加入了堆权值来维护树的形状，然后由三种操作——合并（merge)，按size拆分(split_size)，按值拆分(split_kth)。先说说merge。merge 这个操作是将两颗子树a,b（b中元素大于等于a中的元素）合并。这是我们这就是一个递归的过程：对于a,b中的当前节点x,y，按照他们的堆权值来确定父亲和儿子的关系，然后再往下递归这个过程，接左儿子还是右儿子看具体的值。然后split中要引入一个nodepair的结构来返回（把一棵拆成两棵得要个结构来返回啊），基本的操作跟在bst上找第k大和前k个的值一致。。具体看代码理解吧。。。　不好画图。。。。

?
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
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
/*
    针对的是平衡二叉树那道入门题
*/
 
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
  
  
const int maxn = 200001;
int ans = 0;
struct node{
    int key,data,size;
    node *son[2];
    node(){ key = rand();}
}e[maxn],*root;int ne = 0;
  
struct nodepair{
    node* l,*r;
};
  
nodepair mkpair(node* a,node* b){
    nodepair x;
    x.l = a, x.r = b;
    return x;
}
  
void update(node* x){
    if(x){//判断不能少！
        x->size = 1;
        if(x->son[0]) x->size += x->son[0]->size;
        if(x->son[1]) x->size += x->son[1]->size;
    }
}
  
node* merge(node* a,node *b){
    if(!a) {update(b);return b;}
    if(!b) {update(a);return a;}
    if(a->key <= b->key){
        a->son[1] = merge(a->son[1],b);
        update(a); return a;
    }
    else{
        b->son[0] = merge(a,b->son[0]);
        update(b); return b;
    }
}
  
nodepair split_size(node* a,int k){
    if(!a) return mkpair(NULL,NULL);
    if(!k) return mkpair(NULL,a);
    int ts = a->son[0] ? a->son[0]->size : 0;
    nodepair km;
    if(ts >= k){
        km = split_size(a->son[0],k);
        a->son[0] = km.r; update(a);
        return mkpair(km.l,a);
    }
    else{
        km = split_size(a->son[1],k - ts - 1);
        a->son[1] = km.l; update(a);
        return mkpair(a,km.r);
    }
}
  
nodepair split_kth(node* a,int k){
    if(!a) return mkpair(NULL,NULL);
    nodepair km;
    if(a->data <= k){
        km = split_kth(a->son[1],k);
        a->son[1] = km.l; update(a);
        return mkpair(a,km.r);
    }
    else{
        km = split_kth(a->son[0],k);
        a->son[0] = km.r; update(a);
        return mkpair(km.l,a);
    }
}
  
node* insert(int v){
    node* now = e + ne++;
    now->data = http://www.mamicode.com/v;
    nodepair km = split_kth(root,v);
    return merge(km.l,merge(now,km.r));
}
  
node* del(int v){
    nodepair km1 = split_kth(root,v-1);
    nodepair km2 = split_size(km1.r,1);
    return merge(km1.l,km2.r);
}
  
void askkth(int k){
    node* now = root;
    while(true){
        int ts = now->son[0] ? now->son[0]->size : 0;
        if(ts + 1 == k) break;
        else{
            if(ts >= k) now = now->son[0];
            else k -= ts + 1, now = now->son[1];
        }
    }
    ans = now -> data;
}
  
node* askx(int v){
    nodepair km = split_kth(root,v-1);
    ans = km.l ? km.l->size+1 : 1;
    return merge(km.l,km.r);
}
  
node* pre(int v){
    nodepair km1 = split_kth(root,v-1);
    nodepair km2 = split_size(km1.l,km1.l->size - 1);
    ans = km2.r -> data;
    return merge(merge(km2.l,km2.r),km1.r);
}
  
node* sub(int v){
    nodepair km1 = split_kth(root,v);
    nodepair km2 = split_size(km1.r,1);
    ans = km2.l -> data;
    return merge(km1.l,merge(km2.l,km2.r));
}
  
int n;
  
void read(){
    scanf("%d",&n);
    while(n--){
        int tmp,op;
        scanf("%d%d",&tmp,&op);
        if(tmp == 1) root = insert(op);
        if(tmp == 2) root = del(op);
        if(tmp == 3) root = askx(op);
        if(tmp == 4) askkth(op);
        if(tmp == 5) root = pre(op);
        if(tmp == 6) root = sub(op);
        if(tmp == 3 || tmp == 4 || tmp == 5 || tmp == 6) printf("%d\n",ans);
    }
}
  
int main(){
    read();
    return 0;
}

 

　


联系
我们