记录编号	324236	评测结果	AAAATAAAAT
题目名称	2421.[HZOI 2016] 简单的Treap	最终得分	80
用户昵称	FoolMike	是否通过	未通过
代码语言	C++	运行时间	5.862 s
提交时间	2016-10-17 21:15:35	内存使用	7.13 MiB

#include<cstdio>
#pragma comment(linker, "/STACK:102400000,102400000")
const int N=500010;
int n,l[N],r[N],k[N],ran[N],root;
void l_rotate(int &x){
	int y=r[x];r[x]=l[y];l[y]=x;x=y;
}
void r_rotate(int &x){
	int y=l[x];l[x]=r[y];r[y]=x;x=y;
}
void insert(int &x,int a){
	if (!x){x=a;return;}
	insert(k[a]>k[x]?r[x]:l[x],a);
	if (l[x]&&ran[l[x]]<ran[x]) r_rotate(x);
	if (r[x]&&ran[r[x]]<ran[x]) l_rotate(x);
}
void bianli(int x){
	if (!x) return;
	printf("%d ",k[x]);
	bianli(l[x]);
	bianli(r[x]);
}
int main()
{
	freopen("treap.in","r",stdin);
	freopen("treap.out","w",stdout);
	scanf("%d",&n);
	for (int i=1;i<=n;i++) scanf("%d",&k[i]);
	for (int i=1;i<=n;i++) scanf("%d",&ran[i]);
	for (int i=1;i<=n;i++) insert(root,i);
	bianli(root);puts("");
	return 0;
}