模板汇总——左偏树

class Left_Heap{
public:
    static const int Mn = N;
    int ls[Mn], rs[Mn], rt[Mn], val[Mn], pos[Mn], dis[Mn];
    int n;
    void init(){
        for(int i = 1; i <= n; ++i){
            ls[i] = rs[i] = dis[i] = 0;
            rt[i] = pos[i] = i;
        }
        dis[0] = -1;
    }
    bool cmp(int t1, int t2){
        if(val[t1] == val[t2]) return pos[t1] < pos[t2];
        return val[t1] < val[t2];
    }
    int Find(int x){
        if(x == rt[x]) return x;
        return rt[x] = Find(rt[x]);
    }
    int Merge(int u, int v){
        if(u == v) return u;
        if(!u || !v) return u+v;
        if(!cmp(u, v)) swap(u, v);
        rs[u] = Merge(rs[u], v);
        rt[rs[u]] = u;
        if(dis[ls[u]] < dis[rs[u]]) swap(ls[u], rs[u]);
        dis[u] = dis[rs[u]] + 1;
        return u;
    }
    int Pop(int u){
        if(!u || pos[u] == -1) return -1;
        u = Find(u);
        rt[ls[u]] = ls[u];
        rt[rs[u]] = rs[u];
        rt[u] = Merge(ls[u], rs[u]);
        pos[u] = -1;
        return val[u];
    }
    void Unit(int u, int v){
        if(pos[u] == -1 || pos[v] == -1) return ;
        u = Find(u); v = Find(v);
        if(u == v) return ;
        Merge(u, v);
        return ;
    }
}tr;