[POJ][(裸)笛卡爾樹] 1785 - Binary Search Heap Construction＠Morris' Blog

2014-03-26 19:01:01| 人氣4,286| 回應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;
}

我要檢舉

#1785#Binary Search Heap#Construction#POJ#笛卡爾樹

台長： Morris

您可能對以下文章有興趣

[UVA][SCC、Tarjan算法] 11770 - Lighting Away

[UVA][單調隊列] 12393 - Non-negative Partial Sums

a159. 11743 - Credit Check

[UVA][SSSP] 10947 - Bear with me, again..

人氣(4,286) | 回應(0)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: 教育學習(進修、留學、學術研究、教育概況) | 個人分類: UVA |
此分類下一篇:[UVA][模擬退火] 10228 - Star not a Tree
此分類上一篇:[UVA][笛卡爾樹RMQ] 11235 - Frequent values

回應(0)