題目來源：
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
中文描述：
有一種二叉樹，叫笛卡爾樹，樹的節(jié)點有兩個值：k和a。k值滿足二叉排序樹的性質(zhì)，a值滿足最小堆的性質(zhì)。即如果某個根節(jié)點root有兩個子節(jié)點left和right，那么left.k < root.k < right.k，且root.a < left.a，root.a <
right.a。給你N(1 <= N <= 50 000)個節(jié)點，問你是否可以構(gòu)造出一棵笛卡爾樹。
題目分析與算法模型
一開始，自己是想根據(jù)最小堆的性質(zhì)，擁有最小a值的那個節(jié)點一定是樹的根，接著再找兩個次小a值的節(jié)點，它們必然是根的兩個子節(jié)點，再根據(jù)k值決定節(jié)點是左兒子還是右兒子，然后再以此類推…………，但是在下一層就不對了。因為并不是樹的下一層節(jié)點的a值一定比上一層節(jié)點的a值大（它們不一定在同一棵子樹）。
可以換一個思維，把注意力放在k值上。要知道，如果對一顆二叉排序樹進行前序搜索，k值是從小到大排序的。如果某個節(jié)點是根，那么它左邊的節(jié)點就構(gòu)成左子樹，它右邊的節(jié)點就構(gòu)成右子樹。現(xiàn)在，那個根節(jié)點是哪一個？就是那個a值最小的節(jié)點！所以，我們可以對k值進行排序，現(xiàn)在整個區(qū)間內(nèi)找到a值最小的節(jié)點，他就是根。接著再在左邊和右邊的區(qū)間內(nèi)各找一個a值最小的節(jié)點，看它們的節(jié)點的k值與根節(jié)點的k值是否滿足二叉排序樹的性質(zhì)，如果滿足，就用相同的方法在左、右區(qū)間遞歸建立子樹；如果不滿足，表示無法構(gòu)成笛卡爾樹。
接下來的問題就是，如何在一區(qū)間里找到最小的a值？最容易想到的就是O(n)復(fù)雜度的線性查找，但在此題中，N最大為50000，并且當(dāng)在一個較大區(qū)間內(nèi)查找到一個最值后，又要在一個較小的區(qū)間內(nèi)查找另一個最值，一些節(jié)點被查找了多次，造成時間的浪費。那么，怎么高效的進行多次的區(qū)間查詢呢？RMQ是一個不錯的解決方法。大致思想是：先對區(qū)間內(nèi)的數(shù)進行預(yù)處理，計算出從某一下標(biāo)開始的某一特定長度的最值。當(dāng)查找某一區(qū)間的最值時，就可以把這個區(qū)間分解成一個或兩個已預(yù)先算出最值得區(qū)間，這樣就可以用O(1)的復(fù)雜度算出最值了。（具體講解請查閱相關(guān)資料）
代碼：
#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;
}