> 以下转载自
> 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; 
> }