[POJ 1785] Binary Search Heap Construction【笛卡尔树】
Problem:
Time Limit: 2000MS | Memory Limit: 30000K |
Description
Read the statement of problem G for the definitions concerning trees. In the following we define the basic terminology of heaps. A heap is a tree whose internal nodes have each assigned a priority (a number) such that the priority of each internal node is less than the priority of its parent. As a consequence, the root has the greatest priority in the tree, which is one of the reasons why heaps can be used for the implementation of priority queues and for sorting.
A binary tree in which each internal node has both a label and a priority, and which is both a binary search tree with respect to the labels and a heap with respect to the priorities, is called a treap. Your task is, given a set of label-priority-pairs, with unique labels and unique priorities, to construct a treap containing this data.
Input
Output
Sample Input
7 a/7 b/6 c/5 d/4 e/3 f/2 g/1 7 a/1 b/2 c/3 d/4 e/5 f/6 g/7 7 a/3 b/6 c/4 d/7 e/2 f/5 g/1 0
Sample Output
(a/7(b/6(c/5(d/4(e/3(f/2(g/1))))))) (((((((a/1)b/2)c/3)d/4)e/5)f/6)g/7) (((a/3)b/6(c/4))d/7((e/2)f/5(g/1)))
Source
Solution:
本题是笛卡尔树 O(n) 建树模板。
笛卡尔树是一种与 Treap 类似的 BST,由两个键值 val 和 key 组成。
其中 val 符合二叉排序树性质(即中序遍历升序),key 符合大根堆性质。
与 Treap 不同的是,笛卡尔树的 key 值是确定的,并不是随机给出的。但是两者建树操作相同。
建树时,首先保证 val 升序,然后用一个 key 值单调递减的单调栈来维护树的右链,寻找合适的位置插入,保证 key 符合堆的性质。图示如下:
注意边界条件,防止访问空指针以及之前的操作中残留的无效数据!
Code: O(Tnlogn) [3600K, 922MS]
#include<cstdio> #include<cstdlib> #include<cstring> #include<cmath> #include<iostream> #include<algorithm> using namespace std; int n, tops; struct Node{ char val[15]; int key; Node *fa, *lc, *rc; inline bool operator < (const Node &node2) const {return strcmp(val, node2.val) < 0;} inline void clear() {fa = lc = rc = NULL;} } CT[50005], *stk[50005]; inline void init(int n){ char *tmp = new char[25]; for(register int i = 1; i <= n; i++) scanf("%s", tmp), sscanf(tmp, "%[^/]/%d", CT[i].val, &CT[i].key); sort(CT + 1, CT + n + 1); // BST Indexes must be ascending delete []tmp; } inline void reset(int n) {for(register int i = 1; i <= n; i++) CT[i].clear();} inline Node* build(int n){ memset(stk, 0, sizeof(stk)), tops = 0; for(register int i = 1; i <= n; i++){ Node *o = NULL; while(tops && CT[i].key > stk[tops]->key) o = stk[tops--]; CT[i].lc = o, CT[i].fa = stk[tops]; if(o) o->fa = &CT[i]; if(stk[tops]) stk[tops]->rc = &CT[i]; stk[++tops] = &CT[i]; } return stk[1]; } inline void inorder(Node *cur){ if(cur->lc) putchar('('), inorder(cur->lc), putchar(')'); printf("%s/%d", cur->val, cur->key); if(cur->rc) putchar('('), inorder(cur->rc), putchar(')'); } int main(){ while(scanf("%d", &n) != EOF && n){ init(n); Node *root = build(n); putchar('('), inorder(root), puts(")"); reset(n); // Reset information of pointers } return 0; }
发表评论