左偏树

左偏树是一种可合并堆。可合并堆具体有fibonacci堆，二项堆和左偏树等，左偏树是其中较好实现的一种。

它满足一下几个性质，我总结为堆性、左偏性和递归性。顾名思义，堆性就是满足大（小）根堆的性质——子树的根的关键字大（小）于其两个孩子。左偏性，指每个节点左孩子的dist不小于右孩子（下一段再介绍dist值)，即 [tex]dist(left child) \ge dist(right child)[/tex]。递归性指一个节点的左右孩子都是左偏树。

dist值的定义为 [tex]dist(n) =\begin{cases} -1,&\mbox{if }n\mbox{ is null} \\dist(right child)+1,&\mbox{otherwise}\end{cases}[/tex]

zoj2334是左偏树最简单应用，加个读入优化就rank1了

代码很短，见下：

#include<cstdio>
#include<cstring>
#include<climits>
#define maxn 1000005
int n,m,tot,root[maxn],v[maxn],l[maxn],r[maxn],d[maxn],father[maxn];
void swap(int &a,int &b){
    int c = a;a = b;b = c;
}
int merge(int x,int y){
    if(!x) return y;
    if(!y) return x;
    if(v[x] < v[y]) swap(x,y);
    r[x] = merge(r[x],y);
    if(d[l[x]] < d[r[x]]) swap(l[x],r[x]);
    d[x] = d[r[x]] + 1;
    return x;
}
int init(int x){l[tot] = r[tot] = d[tot] = 0;v[tot++] = x;return tot-1;}
int insert(int x,int y){return merge(x,init(y));}
int top(int x){return v[x];}
int pop(int x){return merge(l[x],r[x]);}
int getfather(int x){
    if(x == father[x]) return x;
    father[x] = getfather(father[x]);
    return father[x];
}
int getint(){
    char c = getchar();
    int ret = 0;
    while(c < '0' || c > '9') c = getchar();
    while(c >= '0' && c <= '9'){
        ret = ret * 10 + c - '0';
        c = getchar();
        }
    return ret;
}     
int main(){
    while(scanf("%d",&n) == 1){
        tot = 0;
        for(int i = 1;i<=n;i++) father[i] = i;
        for(int i = 1;i<=n;i++){
            int a = getint();
            root[i] = init(a);
            }
        scanf("%d",&m);
        for(int i = 0;i<m;i++){
            int x = getint(),y = getint();
            if((x = getfather(x)) == (y = getfather(y))) {printf("-1\n");continue;}
            int a = top(root[x]),b = top(root[y]);
            root[x] = pop(root[x]);
            root[x] = insert(root[x],a >> 1);
            root[y] = pop(root[y]);
            root[y] = insert(root[y],b >> 1);
            father[x] = y;
            root[y] = merge(root[y],root[x]);
            printf("%d\n",top(root[y]));
         }
         }
    return 0;
}          

apio2012的dispatching就可以用左偏树实现。对每个人根据薪水建立一个大根左偏树。按照拓扑序，访问节点时，不断去除最大值，直到剩余薪水和小于m，更新最大值，并将自己的左偏树合并入其上级的左偏树中即可。

代码同样很短,见下：

#include<cstdio>
#include<cstring>
#include<climits>
#include<queue>
using namespace std;
#define maxn 100005
int n,root[maxn],v[maxn],d[maxn],l[maxn],r[maxn],L[maxn],C[maxn],B[maxn],tot,de[maxn];
long long m,Max,ans[maxn],sum[maxn];
queue<int> Q;
void swap(int &a,int &b){
    int c = a;a = b;b = c;
}
int merge(int x,int y){
	if(!x) return y;
    if(!y) return x;
    if(v[x] < v[y]) swap(x,y);
    r[x] = merge(r[x],y);
    if(d[l[x]] < d[r[x]]) swap(l[x],r[x]);
    d[x] = d[r[x]] + 1;
    return x;
}
int init(int x){v[tot++] = x;return tot-1;}
int top(int x){return v[x];}
int pop(int x){return merge(l[x],r[x]);}
int insert(int x,int y){return merge(x,init(y));}
int getint(){
    char c = getchar();
    int ret = 0;
    while(c < '0' || c > '9') c = getchar();
    while(c >= '0' && c <= '9'){
        ret = ret * 10 + c - '0';
        c = getchar();
        }
    return ret;
} 
int main(){
    scanf("%d%lld",&n,&m);
    tot = 1;
    for(int i = 1;i<=n;i++){
        B[i] = getint(),C[i] = getint(),L[i] = getint();
        if(B[i]) de[B[i]]++;
        root[i] = init(C[i]);
        ans[i] = 1;
        sum[i] = C[i];
        }
    for(int i = 1;i<=n;i++) if(!de[i]) Q.push(i);
    while(!Q.empty()){
        int q = Q.front();
        Q.pop();
        while(sum[q] > m){
            sum[q] -= top(root[q]);
            root[q] = pop(root[q]);
            ans[q]--;
            }
        if(Max < (long long)ans[q] * (long long) L[q]) Max = (long long) ans[q] * (long long) L[q];
        root[B[q]] = merge(root[B[q]],root[q]);
        ans[B[q]] += ans[q];
        sum[B[q]] += sum[q];
        de[B[q]]--;
        if(!de[B[q]]) Q.push(B[q]);
        }
    printf("%lld\n",Max);
    return 0;
}