```cpp
//巨丑的代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#define MN 500005
#define inf 2147483647
#define re register int
using namespace std;
int son[MN*50][2],val[MN*50],rnd[MN*50],size[MN*50];
int cnt,n,m,root[MN],x,y,z;
void pushup(int x){size[x]=size[son[x][0]]+size[son[x][1]]+1;}
int add(int x){
val[++cnt]=x;
size[cnt]=1;
rnd[cnt]=rand();
return cnt;
}
void split(int now,int k,int &x,int &y){
if(!now)x=y=0;
else {
if(val[now]<=k)
{
x=++cnt;
val[x]=val[now];
rnd[x]=rnd[now];
size[x]=size[now];
son[x][1]=son[now][1];
son[x][0]=son[now][0];
split(son[x][1],k,son[x][1],y);
pushup(x);
}
else {
y=++cnt;
val[y]=val[now];
rnd[y]=rnd[now];
size[y]=size[now];
son[y][1]=son[now][1];
son[y][0]=son[now][0];
split(son[y][0],k,x,son[y][0]);
pushup(y);
}
}
}
int merge(int p,int q){
if(!p||!q)return p+q;
if(rnd[p]<rnd[q]){
son[p][1]=merge(son[p][1],q);
pushup(p);
return p;
}
else {
son[q][0]=merge(p,son[q][0]);
pushup(q);
return q;
}
}
int kth(int now,int k)
{
if(k<=size[son[now][0]])return kth(son[now][0],k);
else if(k==size[son[now][0]]+1) return now;
else {k-=(size[son[now][0]]+1);return kth(son[now][1],k);}
}
int main(){
scanf("%d",&n);
for(re i=1;i<=n;i++){
int a1,a2,a3;
scanf("%d%d%d",&a1,&a2,&a3);
root[i]=root[a1];
if(a2==1){
split(root[i],a3,x,y);
root[i]=merge(merge(x,add(a3)),y);
}
if(a2==2){
split(root[i],a3,x,z);
split(x,a3-1,x,y);
y=merge(son[y][0],son[y][1]);
root[i]=merge(merge(x,y),z);
}
if(a2==3){
split(root[i],a3-1,x,y);
printf("%d\n",size[x]+1);
root[i]=merge(x,y);
}
if(a2==4){
printf("%d\n",val[kth(root[i],a3)]);
}
if(a2==5){
split(root[i],a3-1,x,y);
if(x)printf("%d\n",val[kth(x,size[x])]);
else printf("-2147483647\n");
root[i]=merge(x,y);
}
if(a2==6){
split(root[i],a3,x,y);
if(y)printf("%d\n",val[kth(y,1)]);
else printf("2147483647\n");
root[i]=merge(x,y);
}
}
return 0;
}
```
by 红色OI再临 @ 2019-07-03 19:10:03
所以如何严格证明merge时不用新建结点呢？
by WAutomaton @ 2019-07-07 12:02:40