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