2018-team4-modules-左偏树

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

{{{
struct Node{
    Node *ch[2];
    int dis,val;
    void update();
    bool judge();
}mem[maxn],*it,*null,*root[maxn];
void Node::update(){
    if(ch[0] == null && ch[1] == null) dis = 0;
    else dis = ch[1]->dis + 1;
}
bool Node::judge(){
    if(ch[0] == null) return true;
    if(ch[1] == null) return false;
    return ch[0]->dis < ch[1]->dis;
}
void init(){
    it = mem;null = it++;
    null->ch[0] = null->ch[1] = null;
    null->dis = 0;null->val = 0;
}
Node* newNode(int x){
    Node *p = it++;
    p->ch[0] = p->ch[1] = null;
    p->dis = 0;p-> val = x;
    return p;
}
Node* merge(Node *u,Node *v){
    if(u == null) return v;
    if(v == null) return u;
    if(u->val < v->val) swap(u,v);
    u->ch[1] = merge(u->ch[1],v);
    if(u->judge()) swap(u->ch[0],u->ch[1]);
    u->update();return u;
}
int top(Node* &u){
    int ret = u->val;
    u = merge(u->ch[0],u->ch[1]);
    return ret;
}
}}}

struct Node{
    Node *ch[2];
    int dis,val;
    void update();
    bool judge();
}mem[maxn],*it,*null,*root[maxn];
void Node::update(){
    if(ch[0] == null && ch[1] == null) dis = 0;
    else dis = ch[1]->dis + 1;
}
bool Node::judge(){
    if(ch[0] == null) return true;
    if(ch[1] == null) return false;
    return ch[0]->dis < ch[1]->dis;
}
void init(){
    it = mem;null = it++;
    null->ch[0] = null->ch[1] = null;
    null->dis = 0;null->val = 0;
}
Node* newNode(int x){
    Node *p = it++;
    p->ch[0] = p->ch[1] = null;
    p->dis = 0;p-> val = x;
    return p;
}
Node* merge(Node *u,Node *v){
    if(u == null) return v;
    if(v == null) return u;
    if(u->val < v->val) swap(u,v);
    u->ch[1] = merge(u->ch[1],v);
    if(u->judge()) swap(u->ch[0],u->ch[1]);
    u->update();return u;
}
int top(Node* &u){
    int ret = u->val;
    u = merge(u->ch[0],u->ch[1]);
    return ret;
}