[POJ][(裸)笛卡] 1785 - Binary Search Heap Construction＠Morris' Blog｜PChome Online 人新台

Morris' Blog 我在摸索我存在的意、生命的意、涵及值。有真正神手般的害，套用模式是大部分的情。那害的我存在的意何，托出神的存在？有候不能怪人不我，我已始省思，什我有人的原因，而是全要靠人。有候我我不同，那是因我做不到很多人能到的事情。我不到、玩不起、得不明、理解得不多，我缺少的文能力，就是一切一切能的判定。此，我不得能做些人有助的事情。我知道我自己是不服的性格，但在我不得不。我有能力，因此我必。我到底世界作什？充不定性，而我是法出拔萃，想一般人似乎也回不了了。越大的挑需要越力的支持，而我的支持是什？最近人，但都是失的局，人能接受，不需要言，不需要通，一切所想都表不出。
49的鼓 6站台

2014-03-26 19:01:01| 人4,720| 回0 | 上一篇 | 下一篇

[POJ][(裸)笛卡] 1785 - Binary Search Heap Construction

推 0 收藏 0 0 站台

Binary Search Heap Construction

Time Limit: 2000MS		Memory Limit: 30000K
Total Submissions: 8406		Accepted: 2422

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

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.

Output

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 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

Ulm Local 2004

而只是作笛卡於 RMQ 的，可以在 O(n) - O(1) 完成。

也就是列有 n 字，次有 m ，消耗 O(n+m)。

方法不用有更新的支持。

先稍微一下笛卡 (一二元)，每 <key, value>，只看 key ，笛卡是一棵二元搜，而看 value ，它是一最大堆 (或者是最小堆)。

在建造前，先撇清一，笛卡的深度可能到 n，一般平衡不同。

笛卡如何建造 ? 假使已於 key 值由小到大排序 (升排序)，那依序插入笛卡，能保的是－由於要符合二元搜，新加入的一定是棵某的右。知道一後，再往前考前一次插入的(它原本也符合再某的右)，往往上爬，直到符合最大堆(性 node.v > new_insert.v)，的右子移到新加入的左子 (此符合二元搜的性，也保有原本堆的性)。就持入下去。

，往上爬的次不超，因每只右子到左子。

均下 O(n)

如何利用笛卡解最的 RMQ ，於 <key, value> = <i, A[i]> 所建造的笛卡，可以利用 LCA 的 tarjan 算法(作法) 在 O(n) 完成。

一般最常的是使用 segment tree 完成 RMQ 上查，若要解 LCA 也可以透 Euler travel 成 RMQ 後用 segment tree，如此一是 O(n) - O(log n)。

然而使用笛卡就是 RMQ 成 LCA 的一工具。

#include <stdio.h>
#include <algorithm>
#include <string.h>
using namespace std;
struct Node {
    int index;
    int val, lson, rson, parent;
};
Node D[50005];
char s[50005][105];
bool cmp(int a, int b) {
   return strcmp(s[a], s[b]) < 0;
}
void insertCartesianTree(int index, Node D[]) {
    int p = index - 1;
    while(D[p].val < D[index].val)
        p = D[p].parent;
    D[index].lson = D[p].rson;
    D[p].rson = index;
    D[index].parent = p;
}
void dfsPrint(int node) {
    if(node == 0)    return;
    putchar('(');
    dfsPrint(D[node].lson);
    printf("%s/%d", s[D[node].index], D[node].val);
    dfsPrint(D[node].rson);
    putchar(')');
}
int main() {
    int N, x[50005], A[50005];
    while(scanf("%d", &N) == 1 && N) {
        for(int i = 1; i <= N; i++) {
            scanf(" %[a-z]/%d", s[i], &x[i]);
            A[i] = i;
        }
        sort(A+1, A+1+N, cmp);
        D[0].val = 0x3f3f3f3f;
        D[0].lson = D[0].rson = D[0].parent = 0;
        for(int i = 1; i <= N; i++) {
            D[i].lson = D[i].rson = D[i].parent = 0;
            D[i].val = x[A[i]], D[i].index = A[i];
        }
        for(int i = 1; i <= N; i++) {
            insertCartesianTree(i, D);
        }
        dfsPrint(D[0].rson);
        puts("");
    }
    return 0;
}