2014-03-26 19:01:01Morris
[POJ][(裸)笛卡爾樹] 1785 - Binary Search Heap Construction
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.
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;
}
而這只是實作笛卡爾樹對於 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;
}