笛卡尔树模板

题目链接：http://poj.org/problem?id=2201

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
const int N=50010;
int stack[N];
int pre[N],lson[N],rson[N];
struct node
{
	int key,value,id;
}a[N];
bool operator <(const node &a, const node &b)
{
	return a.key < b.key;
}
void bct(int n)
{
	int k,top=-1;
	for(int i=0;i<n;i++)
	{
		k=top;
		while(k>=0&&a[stack[k]+1].value>a[i+1].value)
		k--;
		if(k!=-1)
		{
			pre[a[i+1].id]=a[stack[k]+1].id;
			rson[a[stack[k]+1].id]=a[i+1].id;
		}
		if(k<top)
		{
			pre[a[stack[k+1]+1].id]=a[i+1].id;
			lson[a[i+1].id]=a[stack[k+1]+1].id;
		}
		stack[++k]=i;
		top=k;
	}
	pre[a[stack[0]+1].id]=0;
}
int main()
{
	int num;
	scanf("%d",&num);
	memset(stack,-1,sizeof(stack));
	for(int i=1;i<=num;i++)
	{
		scanf("%d%d",&a[i].key,&a[i].value);
		a[i].id=i;
	}
	sort(a+1,a+num+1);
	bct(num);
	printf("yes\n");
	for(int i=1;i<=num;i++)
	printf("%d %d %d\n",pre[i],lson[i],rson[i]);
	return 0;
}