以下转载自
http://fanhq666.blog.163.com/blog/static/819434262010630115338448/

最近在做poj3016K-Monotonic
先说说这题怎么做吧。参见Baltic OI 2004 sequence
提供一个网址http://wenku.baidu.com/view/1c18eff9aef8941ea76e051b.html
自己去看就行了。这题就是跑2*N遍sequence，当然了，要先把严格”上升“转化为”不降“。

关键是可并堆的实现。论文中介绍了一个叫”左偏树“的东西，很好很优秀。不过，写起来稍微有点麻烦（至少7行！）
我本着”短代码就是生产力“的思想，希望能够开发一个超级好写的可并堆。怎么办呢？
首先，分析一下左偏树的本质。我们知道，任何一个用二叉树实现的堆（父亲大于儿子的那种），
都是可以合并的，只不过会打乱原来的某些性质（例如二叉堆，合并之后就不是完全二叉树了）
方法如下：
Merge(p,q)
   如果p或q之一是空的(null) return p+q
   if (p中的最小元素（就是他的根）比q中的最小元素大) 交换p,q
   p->左子树  =   Merge(p->左子树,q)        ///**************
   return p
请注意，带*号的那行中左子树是可以替换为右子树的。
这时，我们很纠结：带*的那一行，到底是选左子树和q合并，还是右子树呢？
这两种策略都有可能导致merge的过程花费很差很长的时间。
所谓左偏树，就用了一种启发式的方法来处理这个问题：
让q和p的”距离“短的那个子树合并！而所谓”距离“的定义，就是从这个节点Merge下去可能的最长路径的长度。

如果说左偏树是可并堆中的avl，那么”斜堆“就是可并堆中的splay:每次合并之后，都把左右子交换一下，用均摊分析来保证复杂度。
好了，那有没有可并堆中的treap？
当然！我们有了一个大胆的创意：每次随机和左子树或右子树合并！这就形成了一个随机化的堆：Random Heap
具体实现嘛，就一行，不过有点长，这一行有89个字符
node *M(node *p,node *q){
	return (!p||!q)?(p?p:q):(p->k<q->k?M(q,p):((ran()?p->r=M(p->r,q):p->l=M(p->l,q)),p));//就是这一行
}
数据结构的定义如下：
struct node{node *l,*r;int k;};
还有一个我自己写的随机生成器：
int ran(){static int x=1;x+=(x<<2)+1;	x&=(0x7fffffff);return x&(65536);}
所谓插入，就是合并：x=Merge(x,y)；
所谓弹出最小，就是合并：x=Merge(x->l,x->r)；
有人一听”左偏树“就头疼，其实，"可并堆”不只"左偏树"一个！还有斐波那契堆（更头疼）和随机heap！
就89个字符，就1行，随机heap就是如此简单。
那效率如何？
经过我测试，在poj3016上，随机heap和左偏树跑的时间没有太大差别，只慢一点点（总时间慢6.7%）。
哈哈，曾经不敢触及的“可并堆”在随机化的作用下，变得如此轻松+愉快。

附：我这题的代码：http://cid-354ed8646264d3c4.office.live.com/self.aspx/.Public/3016.cpp
附：左偏树的代码：（其实也没多长，可谁让我懒呢？）
struct node{
	node *l,*r;
	int d,k;
	node(){l=r=NULL;}
};
#define DIST(_) (_?_->d:-1)
#define SWAP(_,__) t=_,_=__,__=t 
node *Merge(node *p,node *q){
	static node *t; if (!p || !q)return p?p:q; 
	if (p->k<q->k)SWAP(p,q);
	p->r=Merge(p->r,q); 
	if (DIST(p->l)<DIST(p->r))SWAP(p->l,p->r);
	return p->d=DIST(p->r)+1,p; 
}

• 大牛牛！ (2006) yc5_yc 2012-07-04 22:05:22
• 楼主的宏定义确实用得很有感觉，很文艺。 (5) Magic347 2012-07-05 00:37:05
  • 没错！ (9) yc5_yc 2012-07-06 17:41:30