[HZOI 2016]简单的Treap

发表于 | 分类于

题目

Treap是一种平衡二叉搜索树，除二叉搜索树的基本性质外，Treap还满足一个性质：
每个节点都有一个确定的优先级，且每个节点的优先级都比它的两个儿子小(即它的优先级满足堆性质)。
不难证明在节点的优先级都事先给定且互不相同时，对应的Treap有且仅有一个。
现在，给定n个数和每个数对应的优先级，求出对应的以数的大小作为二叉搜索树比较依据的Treap的先序遍历结果。
对先序遍历的定义是：先访问根节点，再访问左子树，最后访问右子树。

INPUT

第一行一个数n表示数的个数。
第二行n个数表示每个数的大小。
第三行n个数表示每个数对应的优先级。

OUTPUT

一行n个数，表示Treap的先序遍历结果(对于每个节点，输出对应的数)。

SAMPLE

INPUT

7
2 11 5 9 1 4 3
2 10 1 8 4 6 5

OUTPUT

5 2 1 3 4 9 11

解题报告

不要相信题目名称！！！
这题卡Treap，用Treap会T掉俩点，那么我们就需要黑科技——笛卡尔树来解决问题了。

笛卡尔树

笛卡尔树是一种同时满足二叉搜索树和堆的性质的数据结构。 可在一个数组上构造出来（时间复杂度可以达到O(n))。树中节点有几个属性， key（节点元素的大小）、index（节点在原数组中的索引）、left（左子节点）、right（右子节点）、parent（父节点）。

性质

树中的元素满足二叉搜索树性质，要求按照中序遍历得到的序列为原数组序列
树中节点满足堆性质，节点的key值要大于其左右子节点的key值

构造

要求在给定的数组的基础上构造一棵笛卡尔树，这可以在O(n)的时间内完成。 其具体思路为：
当按照index从1到n（或者从0到n-1）的顺序将数组中的每个元素插入到笛卡尔树中时，当前要被插入的元素的index值最大，因此根据二叉搜索的性质需要沿着当前已经完成的笛卡尔树的根的右子树链搜索。
由于笛卡尔树要满足堆的性质（以最大堆为例），父节点的key值要大于子节点的key值，所以沿着树根的右子树链往下走，直到搜索到的节点的key值小于等于当前要插入节点的key值。
此时，便找到了当前结点需要插入的位置，记为P。此时P下方的节点的key值肯定小于当前被插入节点的key，但是index也小于当前插入节点的index（即需要在二叉搜索树中当前结点之前的位置），所以将当前节点插入到P的位置，同时将以P为根的子树挂载到新插入的节点的左子树（为了保证P及其子树在新插入节点之前被二叉搜索）。
实际实现的时候，可以采用栈的数据结构。栈中保存当前树中的从树根开始的右子节点链，根在栈底部。
插入新元素的时候，从树的右子链的最末尾从下往上查找，直到找到第一个满足堆性质的节点（即找到的节点的key值大于当前需要插入的节点）。用栈来实现就是从栈顶不断弹出元素，直到栈顶的元素的key大于当前结点的key，然后将该节点入栈，同时将最后被弹出的节点的parent指向该节点，以及该节点的左子节点指向最后被弹出的节点。
复杂度分析： 每个节点最多入栈一次，出栈一次，因此时间复杂度为 O(n)

ps:其实没那么麻烦= =，几个数组乱抡就可以了

那么剩下的就很简单了，按关键字排个序，建树，然后乱搞- -

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
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
inline int read(){
	int sum(0);
	char ch(getchar());
	while(ch<'0'||ch>'9')
		ch=getchar();
	while(ch>='0'&&ch<='9'){
		sum=sum*10+ch-'0';
		ch=getchar();
	}
	return sum;
}
struct node{
	int val,key;//val为数的大小，key为优先级- -
	bool operator<(const node &a)const{
		return val<a.val;
	}
}a[500001];
int n;
int stack[500001],top(0);
int root,lc[500001],rc[500001];
inline void print(int u){
	if(u==0)
		return;
	printf("%d ",a[u].val);
	print(lc[u]);
	print(rc[u]);
}
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__));
	n=read();
	for(int i=1;i<=n;i++)
		a[i].val=read();
	for(int i=1;i<=n;i++)
		a[i].key=read();
	sort(a+1,a+n+1);
	for(int i=1;i<=n;i++){
		stack[top+1]=0;
		while(top&&a[stack[top]].key>a[i].key)
			top--;
		lc[i]=stack[top+1];
		if(top==0)
			root=i;
		else
			rc[stack[top]]=i;
		stack[++top]=i;
	}
	print(root);
}