记录编号	369790	评测结果	AAAAAAAAAA
题目名称	[HZOI 2016] 简单的Treap	最终得分	100
用户昵称	AntiLeaf	是否通过	通过
代码语言	C++	运行时间	0.982 s
提交时间	2017-02-11 10:32:16	内存使用	9.83 MiB

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=500010;
struct A{
	int x,p;
	bool operator<(const A &a)const{return x<a.x;}
}a[maxn];
void dfs(int);
int s[maxn],top=0,lc[maxn]={0},rc[maxn]={0},root=0;
int n;
int main(){
	freopen("treap.in","r",stdin);
	freopen("treap.out","w",stdout);
	int __size__=128<<20;
	char *__p__=(char*)malloc(__size__)+__size__;
	__asm__("movl %0, %%esp\n"::"r"(__p__));
	scanf("%d",&n);
	for(int i=1;i<=n;i++)scanf("%d",&a[i].x);
	for(int i=1;i<=n;i++)scanf("%d",&a[i].p);
	sort(a+1,a+n+1);
	for(int i=1;i<=n;i++){
		s[top+1]=0;
		while(top&&a[s[top]].p>a[i].p)top--;
		lc[i]=s[top+1];
		(top?rc[s[top]]:root)=i;
		s[++top]=i;
	}
	dfs(root);
	return 0;
}
void dfs(int x){
	if(!x)return;
	printf("%d ",a[x].x);
	dfs(lc[x]);
	dfs(rc[x]);
}