UVALive3831 Double Queue(普通treap)

大概就是个treap

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
#include <bits/stdc++.h>
using namespace std;
struct node{
int v,r;
node* ch[2];
node(int x,int pri){
this->v=x;
this->r=pri;
this->ch[0]=this->ch[1]=NULL;
}
int cmp(int x)
{
if(x==v) return -1;
return x<v?0:1;
}
};
node *rt=NULL;
void rotate(node* &o,int d)
{
node* k=o->ch[d^1];
o->ch[d^1]=k->ch[d];
k->ch[d]=o;
o=k;
}
void insert(node* &o,int val,int pri)
{
if(o==NULL) {
o=new node(val,pri);
}
else{
int d=(o->v)>val?0:1;
insert(o->ch[d],val,pri);
if((o->ch[d]->r)>o->r) rotate(o,d^1);
}
}
void removeMax(node* &o,node* &pre)
{
if(o==NULL) {printf("0\n");return;}
if(o->ch[1]!=NULL){
removeMax(o->ch[1],o);
}
else{
printf("%d\n",o->r);
if(pre==o){
if(o->ch[0]!=NULL) o=o->ch[0];
else o=NULL;
}else{
if(o->ch[0]!=NULL) o=o->ch[0];
else pre->ch[1]=NULL;
}
}
}
void removeMin(node* &o,node* &pre)
{
if(o==NULL) {printf("0\n");return;}
if(o->ch[0]!=NULL){
removeMin(o->ch[0],o);
}
else{
printf("%d\n",o->r);
if(pre==o){
if(o->ch[1]!=NULL) o=o->ch[1];
else o=NULL;
}else{
if(o->ch[1]!=NULL) o=o->ch[1];
else pre->ch[0]=NULL;
}
}
}
void print(node*& o)
{
if(o==NULL) return;
if(o->ch[0]!=NULL) print(o->ch[0]);
printf("v=%d r=%d ||",o->v,o->r);
if(o->ch[1]!=NULL) print(o->ch[1]);
}
int main()
{
int op,k,p;
while(scanf("%d",&op)==1)
{
if(op==0) rt=NULL;
else if(op==1){
scanf("%d%d",&k,&p);
insert(rt,p,k);
}else if(op==2){
removeMax(rt,rt);
}else if(op==3){
removeMin(rt,rt);
}
}
return 0;
}