【左偏树】HDU1512-Monkey King

【题目大意】

在一个森林里住着N(N<=10000)只猴子。在一开始，他们是互不认识的。但是随着时间的推移，猴子们少不了争斗，但那只会发生在互不认识(认识具有传递性)的两只猴子之间。争斗时，两只猴子都会请出他认识的猴子里最强壮的一只(有可能是他自己)进行争斗。争斗后，这两只猴子就互相认识。每个猴子有一个强壮值，但是被请出来的那两只猴子进行争斗后，他们的强壮值都会减半(例如10会减为5，5会减为2)。现给出每个猴子的初始强壮值，给出M次争斗，如果争斗的两只猴子不认识，那么输出争斗后两只猴子的认识的猴子里最强壮的猴子的强壮值，否则输出 -1。

【思路】

左偏树裸题，一开始一只猴子就是一棵左偏树，然后每次打架先将堆顶删除，力量值减半插入回原来的堆，再合并两个堆，最后输出堆顶即可。

关于左偏树，看这个PPT。

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<algorithm> 
  5 using namespace std;
  6 const int INF=0x7fffffff;
  7 const int MAXN=100000+50;
  8 struct node
  9 {
 10     int key,dis;
 11     int lson,rson;
 12     int father; 
 13 };
 14 node ltree[MAXN];
 15 int n;
 16 
 17 void build(int x,int k)
 18 {
 19     ltree[x].key=k;
 20     ltree[x].father=x;
 21     ltree[x].lson=ltree[x].rson=0;
 22     ltree[x].dis=(x==0)?-1:0;
 23 }
 24 
 25 int find(int x)
 26 {
 27     if (ltree[x].father==x) return x;
 28         else return(find(ltree[x].father));
 29 }
 30 
 31 int merge(int x,int y)
 32 {
 33     if (x==0) return y;
 34     if (y==0) return x;
 35     if (ltree[x].key<ltree[y].key) swap(x,y);
 36     ltree[x].rson=merge(ltree[x].rson,y);
 37     int &l=ltree[x].lson,&r=ltree[x].rson;
 38     ltree[l].father=ltree[r].father=x;
 39     if (ltree[l].dis<ltree[r].dis) swap(l,r);
 40     if (r==0) ltree[x].dis=0;
 41         else ltree[x].dis=ltree[r].dis+1;
 42     return x;
 43 }
 44 
 45 int del(int rt)
 46 {
 47     int l=ltree[rt].lson;
 48     int r=ltree[rt].rson;
 49     ltree[l].father=l;
 50     ltree[r].father=r;
 51     ltree[rt].dis=ltree[rt].lson=ltree[rt].rson=0;
 52     return merge(l,r);
 53 }
 54 
 55 int solve(int x,int y)
 56 {
 57     ltree[x].key>>=1;
 58     ltree[y].key>>=1;
 59     int left,right;
 60     left=del(x);
 61     right=del(y);
 62     left=merge(left,x);
 63     right=merge(right,y);
 64     left=merge(left,right);
 65     return ltree[left].key;
 66 }
 67 
 68 void init()
 69 {
 70     for (int i=1;i<=n;i++)
 71     {
 72         int strong;
 73         scanf("%d",&strong);
 74         build(i,strong);
 75     }
 76     build(0,0);
 77 }
 78 
 79 void get_ans()
 80 {
 81     int q;
 82     scanf("%d",&q);
 83     for (int i=0;i<q;i++)
 84     {
 85         int x,y;
 86         scanf("%d%d",&x,&y);
 87         int fx=find(x),fy=find(y);
 88         if (fx==fy) cout<<-1<<endl;
 89             else cout<<solve(fx,fy)<<endl;
 90     }
 91 }
 92 
 93 int main()
 94 {
 95     while (scanf("%d",&n)!=EOF)
 96     {
 97         init();
 98         get_ans();
 99     } 
100     return 0;    
101 }