題目來源：
PKU
2201 Cartesian Tree
分類：
RMQ
原文：
Cartesian Tree
|
Time Limit: 10000MS
|
|
Memory Limit: 65536K
|
|
Total Submissions: 1196
|
|
Accepted: 423
|
|
Case Time Limit: 2000MS
|
Description
Let us
consider a special type of a binary search tree, called a cartesian tree.
Recall that a binary search tree is a rooted ordered binary tree, such that for
its every node x the following condition is satisfied: each node in its left
subtree has the key less then the key of x, and each node in its right subtree
has the key greater then the key of x.
That is, if we denote left subtree of the node x by L(x), its right subtree by
R(x) and its key by kx then for each node x we have
- if y ∈ L(x) then ky < kx
- if z ∈ R(x) then kz > kx
The binary search tree is called cartesian if its every node x in addition to
the main key kx also has an auxiliary key that we will denote by ax, and for
these keys the heap condition is satisfied, that is
- if y is
the parent of x then ay < ax
Thus a cartesian tree is a binary rooted ordered tree, such that each of its
nodes has a pair of two keys (k, a) and three conditions described are
satisfied.
Given a set of pairs, construct a cartesian tree out of them, or detect that it
is not possible.
Input
The first
line of the input file contains an integer number N -- the number of pairs you
should build cartesian tree out of (1 <= N <= 50 000). The following N
lines contain two numbers each -- given pairs (ki, ai). For each pair |ki|,
|ai| <= 30 000. All main keys and all auxiliary keys are different, i.e. ki
!= kj and ai != aj for each i != j.
Output
On the first
line of the output file print YES if it is possible to build a cartesian tree
out of given pairs or NO if it is not. If the answer is positive, on the
following N lines output the tree. Let nodes be numbered from 1 to N
corresponding to pairs they contain as they are given in the input file. For
each node output three numbers -- its parent, its left child and its right
child. If the node has no parent or no corresponding child, output 0 instead.
The input ensure these is only one possible tree.
Sample Input
7
5
4
2
2
3
9
0
5
1
3
6
6
4
11
Sample Output
YES
2
3 6
0
5 1
1
0 7
5
0 0
2
4 0
1
0 0
3
0 0
Source
Northeastern Europe 2002, Northern Subregion
中文描述：
有一種二叉樹，叫笛卡爾樹，樹的節點有兩個值：k和a。k值滿足二叉排序樹的性質，a值滿足最小堆的性質。即如果某個根節點root有兩個子節點left和right，那么left.k < root.k < right.k，且root.a < left.a，root.a <
right.a。給你N(1 <= N <= 50 000)個節點，問你是否可以構造出一棵笛卡爾樹。
題目分析與算法模型
一開始，自己是想根據最小堆的性質，擁有最小a值的那個節點一定是樹的根，接著再找兩個次小a值的節點，它們必然是根的兩個子節點，再根據k值決定節點是左兒子還是右兒子，然后再以此類推…………，但是在下一層就不對了。因為并不是樹的下一層節點的a值一定比上一層節點的a值大（它們不一定在同一棵子樹）。
可以換一個思維，把注意力放在k值上。要知道，如果對一顆二叉排序樹進行前序搜索，k值是從小到大排序的。如果某個節點是根，那么它左邊的節點就構成左子樹，它右邊的節點就構成右子樹。現在，那個根節點是哪一個？就是那個a值最小的節點！所以，我們可以對k值進行排序，現在整個區間內找到a值最小的節點，他就是根。接著再在左邊和右邊的區間內各找一個a值最小的節點，看它們的節點的k值與根節點的k值是否滿足二叉排序樹的性質，如果滿足，就用相同的方法在左、右區間遞歸建立子樹；如果不滿足，表示無法構成笛卡爾樹。
接下來的問題就是，如何在一區間里找到最小的a值？最容易想到的就是O(n)復雜度的線性查找，但在此題中，N最大為50000，并且當在一個較大區間內查找到一個最值后，又要在一個較小的區間內查找另一個最值，一些節點被查找了多次，造成時間的浪費。那么，怎么高效的進行多次的區間查詢呢？RMQ是一個不錯的解決方法。大致思想是：先對區間內的數進行預處理，計算出從某一下標開始的某一特定長度的最值。當查找某一區間的最值時，就可以把這個區間分解成一個或兩個已預先算出最值得區間，這樣就可以用O(1)的復雜度算出最值了。（具體講解請查閱相關資料）
代碼：
#include
<iostream>
#include
<cmath>
#include
<algorithm>
using
namespace std;
const
int MAX = 50005;
struct
Node
{
int index;
int k, a;
int parent, left, right;
};
Node
node[MAX];
int
left, right;
int
f[MAX][16]; //f[i][j] is
the index of the min a from i
//to
i + 2^j - 1
int
n;
bool
cmpByK (Node n1, Node n2)
{
return ( n1.k < n2.k );
}
bool
cmpByIndex (Node n1, Node n2)
{
return ( n1.index < n2.index );
}
void
Input ()
{
int i;
scanf("%d", &n);
for (i=0; i<n; i++)
{
scanf("%d%d",
&node[i].k, &node[i].a);
node[i].index = i + 1;
}
}
int
Max (int a, int b)
{
return ( a>b?a:b );
}
int
Min (int a, int b)
{
return ( a<b?a:b );
}
void
Initial ()
{
int i, k, m;
sort(node, node+n, cmpByK);
//RMQ
for (i=0; i<n; i++)
f[i][0] = i;
m = floor(log(double(n)) /
log(double(2))) + 1;
for (k=1; k<m; k++)
{
for (i=0; i<n; i++)
{
f[i][k] = f[i][k-1];
if ( i +
(1<<(k-1)) < n )
{
if (
node[f[i][k-1]].a > node[f[i + (1<<(k-1))][k-1]].a )
f[i][k]
= f[i + (1<<(k-1))][k-1];
}
}
}
}
int
MinAIndex (int i, int j)
{
int k;
k = floor( log(double(j-i+1)) /
log(double(2)) );
if (node[f[i][k]].a <= node[f[j -
(1<<k) + 1][k]].a)
return f[i][k];
else
return f[j - (1<<k) +
1][k];
}
bool
MakeTree (int i, int j)
{
if ( i == j )
{
node[i].left = node[i].right =
0;
return true;
}
int rootIndex, leftIndex, rightIndex;
bool check1, check2;
rootIndex = MinAIndex(i, j);
if ( rootIndex != i )
leftIndex = MinAIndex(i,
rootIndex-1);
if ( rootIndex != j )
rightIndex =
MinAIndex(rootIndex+1, j);
check1 = true;
if ( rootIndex != i &&
node[rootIndex].k > node[leftIndex].k )
{
node[rootIndex].left =
node[leftIndex].index;
node[leftIndex].parent =
node[rootIndex].index;
check1 = MakeTree(i,
rootIndex-1);
}
check2 = true;
if ( rootIndex != j &&
node[rootIndex].k < node[rightIndex].k )
{
node[rootIndex].right =
node[rightIndex].index;
node[rightIndex].parent =
node[rootIndex].index;
check2 = MakeTree(rootIndex+1,
j);
}
return ( check1 && check2 );
}
void
Solve ()
{
if ( MakeTree(0, n-1) )
{
printf("YES\n");
sort(node, node+n,
cmpByIndex);
for (int i=0; i<n; i++)
{
printf("%d %d
%d\n", node[i].parent, node[i].left, node[i].right);
}
}
else
{
printf("NO\n");
}
}
int
main ()
{
Input ();
Initial ();
Solve ();
return 0;
}