[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;
}
发表评论