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

ydc的博客

 
 
 

日志

 
 

bzoj 1455 罗马游戏  

2013-03-31 22:44:47|  分类: bzoj |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
为什么我要写这道题呢?因为我要学左偏树
为什么我要学左偏树呢?因为沛神批评过我们:你们都这个时候了怎么连左偏树还不会写!!

左偏树是个很好理解很好写的东西,但是应用范围似乎没那么广啊……
可以参考黄源河的论文,讲的不是一般的清楚

这个题目的删除操作有点麻烦,我使用并查集搞得
如果没有删除的话,我们很容易利用并查集,使得我们的getfather(p)函数一定是p所在的左偏树的根节点吧?
现在有了删除根节点的操作,我们可以这样搞:把左右儿子合并后把根节点的father值赋值为合并后的左偏树的根节点,并且让那个清掉那个新根节点的father,这样就相当于删除了。
具体见程序

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#define MAXN 1000010
#define Rep(i,l,r) for(int i=l;i<=r;i++)
using namespace std;
bool die[MAXN];
int father[MAXN];
void Read(int &digit)
{
digit=0;
char c;
for(c=getchar();c<'0'||c>'9';c=getchar());
for(;c>='0'&&c<='9';digit=digit*10+c-'0',c=getchar());
}
struct Leftist_Tree
{
int son[MAXN][2],dis[MAXN],value[MAXN];
int Merge(int a,int b)
{
if(a==0) return b;
if(b==0) return a;
if(value[a]>value[b]) swap(a,b);
son[a][1]=Merge(son[a][1],b);
if(dis[son[a][1]]>dis[son[a][0]]) swap(son[a][1],son[a][0]);
dis[a]=dis[son[a][1]]+1;
return a;
}
int pop(int a){ return Merge(son[a][0],son[a][1]); }
}tree;
void read()
{
int n;
Read(n);
Rep(i,1,n)
{
Read(tree.value[i]);
father[i]=i;
}
}
int getfather(int p)
{
if(father[p]!=p) father[p]=getfather(father[p]);
return father[p];
}
void ask()
{
char task;
int n,a,b,c;
Read(n);
Rep(i,1,n)
{
for(task=getchar();task!='M'&&task!='K';task=getchar());
if(task=='M')
{
Read(a),Read(b);
if(die[a]||die[b]) continue;
a=getfather(a),b=getfather(b);
if(a==b) continue;
father[a]=father[b]=tree.Merge(a,b);
}
else
{
Read(a);
if(die[a]) printf("0\n");
else
{
die[a=getfather(a)]=true;
printf("%d\n",tree.value[a]);
father[a]=tree.pop(a),father[father[a]]=father[a];
}
}
}
}
int main()
{
read();
ask();
system("pause");
return 0;
}



  评论这张
 
阅读(263)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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