左偏树

#define l 0
#define r 1
struct node
{
	node *ch[2];
	int v, dist;
	node(){}
	node(int v) : v(v) {}
}nil[maxn], *sp[maxn];
int sptop;
void init()
{
	nil->ch[l] = nil->ch[r] = nil;
	nil->v = inf; nil->dist = -1;
	for (int i = 1; i < maxn; i++) sp[++sptop] = nil + i; 	
}
 
inline node* newnode(int v)
{
	sp[sptop]->ch[l] = sp[sptop]->ch[r] = nil;
	sp[sptop]->dist = 0;
	return new (sp[sptop--]) node(v);
}
 
inline void deletenode(node *t)
{
	sp[++sptop] = t;
}
 
inline node* merge(node *a, node *b)
{
	if (a == nil) return b;
	if (b == nil) return a;
	if (b->v < a->v) swap(a, b);
	a->ch[r] = merge(a->ch[r], b);
	if (a->ch[r]->dist > a->ch[l]->dist) swap(a->ch[l], a->ch[r]);
	a->dist = a->ch[r]->dist + 1;
	return a;
}
 
inline void pop(node* &a)
{
	node *t = a;
	a = merge(a->ch[l], a->ch[r]);
	deletenode(a);
}
 
void push(node* &a, int v)
{
	a = merge(a, newnode(v));
}