[POJ 1785] Binary Search Heap Construction【笛卡尔树】

  • 2018-03-02
  • 0
  • 0


Time Limit: 2000MS Memory Limit: 30000K


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.


The input contains several test cases. Every test case starts with an integer n. You may assume that 1<=n<=50000. Then follow n pairs of strings and numbers l1/p1,...,ln/pn denoting the label and priority of each node. The strings are non-empty and composed of lower-case letters, and the numbers are non-negative integers. The last test case is followed by a zero.


For each test case output on a single line a treap that contains the specified nodes. A treap is printed as (< left sub-treap >< label >/< priority >< right sub-treap >). The sub-treaps are printed recursively, and omitted if leafs.

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

Sample Output



Ulm Local 2004


本题是笛卡尔树 O(n) 建树模板。

笛卡尔树是一种与 Treap 类似的 BST,由两个键值 valkey 组成。

其中 val 符合二叉排序树性质(即中序遍历升序),key 符合大根堆性质。

与 Treap 不同的是,笛卡尔树的 key 值是确定的,并不是随机给出的。但是两者建树操作相同。

建树时,首先保证 val 升序,然后用一个 key 值单调递减的单调栈来维护树的右链,寻找合适的位置插入,保证 key 符合堆的性质。图示如下:


Code: O(Tnlogn) [3600K, 922MS]

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){
		Node *root = build(n);
		putchar('('), inorder(root), puts(")");
		reset(n);  // Reset information of pointers
	return 0;






OPEN AT 2017.12.10

Please refresh the page if the code cannot be displayed normally.


- Theme by Qzhai