UVALive5645 Black Box(普通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
94
95
96
97
98
99
100
101
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <cassert>
#include <stack>
using namespace std;
const int maxm=3000000+5;
struct node{
int v,r,siz;
node* ch[2];
void maintain()
{
int s=1;
if(ch[0]!=NULL) s+=ch[0]->siz;
if(ch[1]!=NULL) s+=ch[1]->siz;
siz=s;
}
node(int x){
this->v=x;
this->r=rand();
this->siz=1;
this->ch[0]=this->ch[1]=NULL;
}
int cmp(int x)
{
if(x==v) return -1;
else{
return x<v?0:1;
}
}
};
node* rt;
void rotate(node* &o,int d)
{
node* k=o->ch[d^1];
o->ch[d^1]=k->ch[d];
k->ch[d]=o;
o->maintain();
k->maintain();
o=k;
}
void insert(node* &o,int x)
{
if(o==NULL){
o=new node(x);
return;
}
else{
int d=x<o->v?0:1;
insert(o->ch[d],x);
if(o->ch[d]->r > o->r) rotate(o,d^1);
o->maintain();
}
}
int kth(node* &o,int k)
{
if(o==NULL || o->siz<k || k==0) return -1;
int s=o->ch[0]==NULL?0:o->ch[0]->siz;
if(k==s+1) return o->v;
else if(k<=s) return kth(o->ch[0],k);
else return kth(o->ch[1],k-s-1);
}
void print(node* &o)
{
if(o==NULL) return;
if(o->ch[0]!=NULL) print(o->ch[0]);
printf("v=%d r=%d siz=%d || ",o->v,o->r,o->siz);
if(o->ch[1]!=NULL) print(o->ch[1]);
}
int n,m;
int a[maxm],u[maxm];
stack<int > req;
int kas=0;
int main()
{
scanf("%d",&kas);
for(int z=0;z<kas;z++)
{
if(z>=1) puts("");
memset(a,0,sizeof(a));
memset(u,0,sizeof(u));
rt=NULL;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
for(int i=1;i<=m;i++) scanf("%d",&u[i]);
for(int i=m;i>=1;i--) req.push(u[i]);
int rnk=0;
for(int i=1;i<=n;i++)
{
insert(rt,a[i]);
while(req.size() && rt->siz==req.top()){
req.pop();
rnk++;
printf("%d\n",kth(rt,rnk));
}
}
}
return 0;
}