游客 注册 | 登录
中文 | En

3668 - 笛卡尔树

通过次数

0

提交次数

0

时间限制 : 3 秒 内存限制 : 128 MB
【问题描述】
      笛卡尔树(Cartesian Tree)是一种特殊的二叉搜索树。让我们复习一下：二叉搜索树是一颗有根二叉树，并且对于每个结点x都满足：它左子树中的任何结点的权值都小于x的权值，它右子树中任何结点的权值都大于x的权值。让我们形式化定义：假设x的左子树为L(x)，x的右子树为R(x)，x的权值为k(x)。则一颗满足如下条件的二叉树称为二叉搜索树：
     如果点y在L(x)中，则k(y)<k(x)；如果点z在R(x)中，则k(z)>k(x)。
     一颗二叉搜索树称为笛卡尔树，当且仅当我们给每个点都附加一个权值a(x)，且每个点的a权值都严格小于它左右子树中的点的a权值。也就是说：如果点y是x的父亲，则a(y)<a(x)。
     因此，一颗笛卡尔树就是一颗二叉树，对于每个结点有两个权值(k,a)，且满足上面三条性质。
     给定一个点，请你构造出一颗笛卡尔树。

题目输入

第一行是一个整数n(1=<n<=50000)，表示给定结点的个数。
接下来n行，每行两个整数k(i)，a(i)，表示点i的两个权值。题目保证同类权值不出现重复，也就是说对于任意i<>j，一定有k(i)<>k(j)，且a(i)<>a(j)。权值都是不超过50000的正整数。

题目输出

第一行输出解的情况。如果可以构造出一颗笛卡尔树，输出"yes"，否则输出"no"。
如果可以构造，那么接下来输出n行，每行3个整数，分别表示第i个结点的父亲、左儿子、右儿子的编号。顶点编号都是从1到n的，0表示空。顶点的输出顺序与输入顺序一致。

输入/输出样例

输入格式

7
5 4
2 2
3 9
0 5
1 3
6 6
4 11

输出格式

yes
2 3 6
0 5 1
1 0 7
5 0 0
2 4 0
1 0 0
3 0 0

C++解答

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=50000;
struct node{int id,k,a;}t[N+1];
int f[N+1],l[N+1],r[N+1],d[N+1];
int i,n;
bool cmp(node x,node y){return x.k<y.k;}
void build()
{
	int k,top=-1;
	for(i=1;i<=n;i++)
	{
		k=top;
		while(k>=0&&t[d[k]].a>t[i].a)
			k--;
		if(k!=-1)
		{
			f[t[i].id]=t[d[k]].id;
			r[t[d[k]].id]=t[i].id;
		}
		if(k<top)
		{
			f[t[d[k+1]].id]=t[i].id;
			l[t[i].id]=t[d[k+1]].id;
		}
		d[++k]=i;
		top=k;
	}
}
int main()
{
	while(~scanf("%d",&n))
	{
		memset(f,0,sizeof(f));
		memset(l,0,sizeof(l));
		memset(r,0,sizeof(r));
		for(i=1;i<=n;i++)
			scanf("%d%d",&t[i].k,&t[i].a),t[i].id=i;
		sort(t+1,t+n+1,cmp);
		build();
		printf("yes\n");
		for(i=1;i<=n;i++)
			printf("%d %d %d\n",f[i],l[i],r[i]);
	}
	return 0;
}
请先登陆