题目来源：
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;
}