洛谷 P1456 Monkey King（左偏树）

传送门

解题思路

更正题意：“输出决斗后他们朋友中最强壮的猴子的强壮值”指的是决斗前最强壮的猴子的决斗后的强壮值（根据样例得出）

所以这题就很板子了。

维护一个有合并、删除、单点插入的左偏树即可。

注意：

多组数据的数组初始化处理。
根节点猴子强壮值减半后对其结构体和fa[x]的重新初始化。

AC代码

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 using namespace std;
 5 const int maxn=100005;
 6 int n,m,fa[maxn],a[maxn];
 7 struct node{
 8     int ls,rs,dis;
 9 }t[maxn];
10 int find(int x){
11     return x==fa[x]?x:fa[x]=find(fa[x]);
12 }
13 void pushup(int x){
14     if(t[t[x].rs].dis>t[t[x].ls].dis) swap(t[x].rs,t[x].ls);
15     t[x].dis=t[t[x].rs].dis+1;
16 }
17 int merge(int x,int y){
18     if(!x||!y) return x|y; 
19     if(a[x]<a[y]) swap(x,y);
20     t[x].rs=merge(t[x].rs,y);
21     fa[t[x].rs]=x;
22     pushup(x);
23     return x;
24 }
25 void goout(int x){
26     fa[t[x].rs]=t[x].rs;
27     fa[t[x].ls]=t[x].ls;
28     int newtop=merge(t[x].rs,t[x].ls);
29     fa[x]=x;
30     t[x].dis=t[x].ls=t[x].rs=0;
31     a[x]/=2;
32     merge(x,newtop);
33 }
34 int main(){
35     while(scanf("%d",&n)!=EOF){
36         for(int i=1;i<=n;i++){
37             fa[i]=i;
38             t[i].dis=t[i].ls=t[i].rs=0;
39         }
40         for(int i=1;i<=n;i++) scanf("%d",&a[i]);
41         scanf("%d",&m);
42         for(int i=1;i<=m;i++){
43             int x,y;
44             scanf("%d%d",&x,&y);
45             x=find(x);
46             y=find(y);
47             if(x==y){
48                 printf("-1
");
49                 continue;
50             }
51             int newtop=merge(x,y);
52             goout(newtop);
53             printf("%d
",a[newtop]);
54         }
55     }
56     return 0;
57 }