642 字
3 分钟
COGS 2421 简单的Treap
【题目描述】
Treap是一种平衡二叉搜索树，除二叉搜索树的基本性质外，Treap还满足一个性质： 每个节点都有一个确定的优先级，且每个节点的优先级都比它的两个儿子小(即它的优先级满足堆性质)。 不难证明在节点的优先级都事先给定且互不相同时，对应的Treap有且仅有一个。 现在，给定n个数和每个数对应的优先级，求出对应的以数的大小作为二叉搜索树比较依据的Treap的先序遍历结果。 对先序遍历的定义是：先访问根节点，再访问左子树，最后访问右子树。
【输入格式】
第一行一个数n表示数的个数。 第二行n个数表示每个数的大小。 第三行n个数表示每个数对应的优先级。
【输出格式】
一行n个数，表示Treap的先序遍历结果(对于每个节点，输出对应的数)。
【样例输入】
7
2 11 5 9 1 4 3
2 10 1 8 4 6 5
【样例输出】
5 2 1 3 4 9 11
【样例解释】
对应的Treap如图所示，其中圈内的数是给出的数，圈外的数是节点的优先级。
【数据范围】
n<=500000。 所有的数和优先级都互不相同且在int(C++)/longint(Pascal)范围内。
【提示】
为了给不想用栈模拟递归的孩纸们偷懒的机会，C++选手请在main函数的开头加入以下代码：
int __size__=128<<20;char *__p__=(char*)malloc(__size__)+__size__;__asm__("movl %0, %%esp\n"::"r"(__p__));注意上述代码会占用你128MB的空间，请自行调整代码。
题解
其实就是排序后用笛卡尔树建一颗树
所以这道题是一道笛卡尔树的裸题
#include <cstdio>#include <vector>#include <algorithm>using namespace std;class data{ public: int v, key; bool operator<(const data &a) const { return v < a.v; }} a[500005];class Node{ public: Node *ch[2]; int key, v; Node(data x) { key = x.key; v = x.v; ch[0] = ch[1] = NULL; } ~Node();} * st[500005];Node *build(int m){ Node *x, *last; int p = 0; for (int i = 1; i <= m; i++) { x = new Node(a[i]); last = NULL; while (p && st[p]->key > x->key) { last = st[p]; st[p--] = NULL; } if (p) st[p]->ch[1] = x; x->ch[0] = last; st[++p] = x; } return st[1];}void dfs(Node *a){ if (a) { printf("%d ", a->v); dfs(a->ch[0]); dfs(a->ch[1]); }}int main(){ int __size__ = 128 << 20; char *__p__ = (char *)malloc(__size__) + __size__; __asm__("movl %0, %%esp\n" ::"r"(__p__)); freopen("treap.in","r",stdin); freopen("treap.out","w",stdout); int n; scanf("%d", &n); for (int i = 1; i <= n; i++) scanf("%d", &a[i].v); for (int i = 1; i <= n; i++) scanf("%d", &a[i].key); sort(a + 1, a + n + 1); Node *rt = build(n); dfs(rt);}