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
| #include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
inline const int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(x<'0'||x>'9') {
if(x=='-')bj=-1;
x=getchar();
}
while(x>='0'&&x<='9') {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}
#define pii pair<int,int>
#define mp make_pair
mt19937 g(rand());
int max(int a,int b) {
return a>b?a:b;
}
const int maxn=300005;
struct Tree {
int l,r,size;
int val;
Tree(int _l=0,int _r=0,int s=0,int v=0):l(_l),r(_r),size(s),val(v) {}
};
struct Treap {
Tree tree[maxn*100];
int size;
#define val(x) tree[x].val
#define size(x) tree[x].size
Treap() {
size=0;
}
int newnode(int v) {
tree[++size]=Tree(0,0,1,v);
return size;
}
void push_up(int index) {
int l=tree[index].l,r=tree[index].r;
size(index)=size(l)+size(r)+1;
}
pii split(int index,int num) {
if(!index)return mp(0,0);
int l=tree[index].l,r=tree[index].r;
int now=++size;
tree[now]=tree[index];
if(num<=size(l)) {
pii lt=split(l,num);
tree[now].l=lt.second;
push_up(now);
return mp(lt.first,now);
} else {
pii rt=split(r,num-size(l)-1);
tree[now].r=rt.first;
push_up(now);
return mp(now,rt.second);
}
}
int merge(int a,int b) {
if(!a||!b)return a+b;
int now=++size;
if(g()%(size(a)+size(b))<size(a)) {
tree[now]=tree[a];
tree[now].r=merge(tree[a].r,b);
} else {
tree[now]=tree[b];
tree[now].l=merge(a,tree[b].l);
}
push_up(now);
return now;
}
int find_rank(int index,int k) {
if(!index)return 0;
if(k<=size(tree[index].l))return find_rank(tree[index].l,k);
else if(k==size(tree[index].l)+1)return index;
else return find_rank(tree[index].r,k-size(tree[index].l)-1);
}
} bbt;
int q,root[maxn],cnt=0;
int main() {
srand(time(NULL));
q=Get_Int();
for(int i=1; i<=q; i++) {
int opt=Get_Int(),t=Get_Int(),k=Get_Int();
if(opt==1) {
pii tmp=bbt.split(root[t],k-1);
root[++cnt]=bbt.merge(bbt.merge(tmp.first,bbt.newnode(Get_Int())),tmp.second);
} else if(opt==2)root[++cnt]=bbt.merge(bbt.split(root[t],k-1).first,bbt.split(root[t],k).second);
else if(opt==3)printf("%d\n",bbt.tree[bbt.find_rank(root[t],k)].val);
}
return 0;
}
|
