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);
}