学步园

并查集显然要用到

左偏树解决合并的问题

这题体现了数据结构的强大啊！

#include<stdio.h>
#include <algorithm>
using namespace std;
const int MAXN = 100100;
int father[MAXN];
struct Monkey{    
int l,r;    
int dis;    
int strong;
}LTree[MAXN];
int find(int x){    
if(x != father[x])        
        father[x] = find(father[x]);    
return father[x];
}
int merge(int x,int y){                        //返回合并后的根    
    if( x == 0 )        
return y;    
if( y == 0)        
return x;    
if( LTree[x].strong < LTree[y].strong)            //大顶堆        
        swap(x,y);    LTree[x].r = merge(LTree[x].r,y);            //递归合并右子树和Y    
    int l = LTree[x].l , r = LTree[x].r;    
    father[r] = x;                        //更新T右子树的根     
    if(LTree[l].dis < LTree[r].dis)                //维护堆性质        
    swap(LTree[x].l,LTree[x].r);    
if(LTree[x].r == 0)                    //如果没有右子树 则距离为0        
        LTree[x].dis = 0;    
else        
        LTree[x].dis = LTree[LTree[x].r].dis + 1;    
return x;
}
int del(int x){            //返回删除根以后左右子树的合并的根    
    int l,r;    
    l = LTree[x].l;    
    r = LTree[x].r;    
    father[l] = l;    
    father[r] = r;    
    LTree[x].l = LTree[x].r = LTree[x].dis = 0;    
return merge(l,r);
}
void solve(int x,int y){    
    LTree[x].strong /= 2;    
    LTree[y].strong /= 2;    //问每次PK以后，当前这个群体里力量最大的猴子的力量是多少。    
    int left,right;    
    left = del(x);    
    right = del(y);    
    left = merge(left,x);    
    right = merge(right,y);    
    left = merge(left,right);    
    printf("%d\n",LTree[left].strong);
}
int main(){        
int n,m,i,x,y;    
while(scanf("%d",&n) == 1){        
for(i = 1; i <= n; i++){            
            scanf("%d",<ree[i].strong);            
            LTree[i].l = 0;            
            LTree[i].r = 0;            
            LTree[i].dis = 0;            
            father[i] = i;            //起始已自己为父亲        
        }        
        scanf("%d",&m);        
for(i = 1; i <= m; i++){            
            scanf("%d%d",&x,&y);            
int fx = find(x),fy = find(y);            
if(fx == fy){                
                printf("-1\n");            
            } else {                
                solve(fx,fy);            
            }       
        } 
    }
return 0;
}