数据结构/可并堆
啊……换换脑子就看了看数据结构……看了一下左偏树和斜堆，鉴于左偏树不像斜堆可能退化就写了个左偏树。
左偏树介绍：http://www.cnblogs.com/crazyac/articles/1970176.html
体会：合并操作是可并堆的核心操作（就像LCT里的access），进堆和弹堆顶都是直接调用合并操作实现的。
而合并的实现是一个递归的过程：将小堆与大堆的右儿子合并（这里的大小指的是堆顶元素的大小），直到某个为0。（是不是有点启发式合并的感觉……）
在合并的过程中要维护堆的形态：如果右儿子长度（或者叫深度？）大于左儿子，那就交换左右儿子。也就是说：每次要生长的时候，总是让短的一侧先生长，那么这个堆，最后就能够比较对称。
1 //HDOJ 1512 2 #include<vector> 3 #include<cstdio> 4 #include<cstring> 5 #include<cstdlib> 6 #include<iostream> 7 #include<algorithm> 8 #define rep(i,n) for(int i=0;i<n;++i) 9 #define F(i,j,n) for(int i=j;i<=n;++i) 10 #define D(i,j,n) for(int i=j;i>=n;--i) 11 #define pb push_back 12 using namespace std; 13 inline int getint(){ 14 int v=0,sign=1; char ch=getchar(); 15 while(ch<'0'||ch>'9'){ if (ch=='-') sign=-1; ch=getchar();} 16 while(ch>='0'&&ch<='9'){ v=v*10+ch-'0'; ch=getchar();} 17 return v*sign; 18 } 19 const int N=1e6+10,INF=~0u>>2; 20 typedef long long LL; 21 /******************tamplate*********************/ 22 int n,m; 23 struct node{ 24 int v,l,r,dis,f; 25 node(int v=0,int l=0,int r=0,int dis=0,int f=0): 26 v(v),l(l),r(r),dis(dis),f(f){} 27 void out(){ 28 printf("%d %d %d %d %d ",v,l,r,dis,f); 29 } 30 }; 31 struct Left_tree{ 32 node t[N]; 33 int merge(int x,int y){ 34 if (x==0) return y; 35 if (y==0) return x; 36 if (t[x].v<t[y].v) swap(x,y); 37 t[x].r=merge(t[x].r,y); 38 t[t[x].r].f=x; 39 if (t[t[x].l].dis<t[t[x].r].dis) swap(t[x].l,t[x].r); 40 if (t[x].r==0) t[x].dis=0; 41 else t[x].dis=t[t[x].r].dis+1; 42 return x; 43 } 44 int pop(int x){ 45 int l=t[x].l,r=t[x].r; 46 t[l].f=l; t[r].f=r; 47 t[x].l=t[x].r=t[x].dis=0; 48 return merge(l,r); 49 } 50 int find(int x){return t[x].f==x ? x : find(t[x].f);} 51 void init(){ 52 int x=0; 53 F(i,1,n){ 54 x=getint(); 55 t[i]=node(x); 56 t[i].f=i; 57 } 58 } 59 void solve(){ 60 m=getint(); 61 int x,y; 62 F(i,1,m){ 63 x=getint(); y=getint(); 64 int f1=find(x),f2=find(y); 65 if (f1==f2){puts("-1");continue;} 66 int t1=pop(f1),t2=pop(f2); 67 t[f1].v/=2; t1=merge(t1,f1); 68 t[f2].v/=2; t2=merge(t2,f2); 69 t1=merge(t1,t2); 70 printf("%d ",t[t1].v); 71 } 72 } 73 }heap; 74 int main(){ 75 #ifndef ONLINE_JUDGE 76 freopen("1512.in","r",stdin); 77 freopen("1512.out","w",stdout); 78 #endif 79 while(scanf("%d",&n)!=EOF){ 80 heap.init(); heap.solve(); 81 } 82 return 0; 83 }