QuXiao

每天进步一点点!

  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::
  50 随笔 :: 0 文章 :: 27 评论 :: 0 Trackbacks
题目来源:

                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

 

 

 

 

中文描述:

                有一种二叉树,叫笛卡尔树,树的节点有两个值:kak值满足二叉排序树的性质,a值满足最小堆的性质。即如果某个根节点root有两个子节点leftright,那么left.k < root.k < right.k,且root.a < left.aroot.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;

}

 

posted on 2008-04-25 21:27 quxiao 阅读(992) 评论(1)  编辑 收藏 引用 所属分类: ACM

评论

# re: PKU 2201 Cartesian Tree[未登录] 2009-05-12 12:20 k
笛卡尔树在排好序的情况下有o(n)构造法  回复  更多评论
  


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理