注册 登录  
 加关注
查看详情
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

Yavin(某沙茶的代码库)

Star Wars fan and OIer

 
 
 

日志

 
 

SGU155(笛卡尔树)  

2012-02-27 20:44:17|  分类: SGU100系列 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

笛卡尔树

先按第一个权值排个序

接下来就只是简单的笛卡尔树了

#include<cstdio>

int n;
const int MAX=50000+10;

struct node
{
int k,a,place;
};
node num[MAX];

int left[MAX],right[MAX],fa[MAX];
int stack[MAX],top;

int point[MAX];

void qsort(int l,int r)
{
int i=l,j=r;
node x=num[(l+r)/2],t;
while(i<=j)
{
while(num[i].k<x.k)++i;
while(num[j].k>x.k)--j;
if(i<=j)
{
t=num[i];num[i]=num[j];num[j]=t;
++i;--j;
}
}
if(l<j)qsort(l,j);
if(i<r)qsort(i,r);
}

int main()
{
freopen("155.in","r",stdin);freopen("155.out","w",stdout);
int i;
scanf("%d",&n);
for(i=1;i<=n;++i)
scanf("%d %d",&num[i].k,&num[i].a);
for(i=1;i<=n;++i)
num[i].place=i;
qsort(1,n);
stack[++top]=1;
num[0].a=-1000000000;
for(i=2;i<=n;++i)
{
while(top>=0&&num[i].a<num[stack[top]].a)
--top;
if(top)
{
fa[i]=stack[top];
left[i]=right[stack[top]];
fa[right[stack[top]]]=i;
right[stack[top]]=i;
stack[++top]=i;
}else
{
fa[stack[1]]=i;
left[i]=stack[1];
stack[++top]=i;
}
}

for(i=1;i<=n;++i)point[num[i].place]=i;
printf("YES\n");
for(i=1;i<=n;++i)
printf("%d %d %d\n",num[fa[point[i]]].place,num[left[point[i]]].place,num[right[point[i]]].place);
}


  评论这张
 
阅读(256)| 评论(0)

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018