P1456 Monkey King

题目地址：[P1456 Monkey King](https://www.luogu.org/problemnew/show/P1456) 一道~~挺模板的~~左偏树题 不会左偏树？看[论文](https://wenku.baidu.com/view/20e9ff18964bcf84b9d57ba1.html)打[模板](https://www.luogu.org/problemnew/show/P3377)，完了之后再回来吧 ~~然后你发现看完论文打完模板之后就可以A掉这道题不用回来了~~ 细节见代码 ``` #include <bits/stdc++.h> using namespace std; const int N = 1e5 + 6; int n, m, f[N], a[N], l[N], r[N], d[N]; //类并查集路径压缩 int get(int x) { if (x == f[x]) return x; return f[x] = get(f[x]); } //左偏树合并 inline int merge(int x, int y) { if (!x || !y) return x + y;//x或y为0则返回另一个的简写 if (a[x] < a[y]) swap(x, y);//保证堆性质 r[x] = merge(r[x], y); f[r[x]] = x; if (d[l[x]] < d[r[x]]) swap(l[x], r[x]);//保证左偏树性质 d[x] = d[r[x]] + 1; return x; } //删除堆顶，注意语句顺序 inline void pop(int x) { f[l[x]] = l[x], f[r[x]] = r[x]; f[x] = merge(l[x], r[x]); l[x] = r[x] = 0; } //多组数据单独写一个函数 inline void work() { d[0] = -1;//0的“距离”为-1 for (int i = 1; i <= n; i++) { scanf("%d", &a[i]); f[i] = i; d[i] = l[i] = r[i] = 0;//多组数据清空数组 } cin >> m; while (m--) { int x, y; scanf("%d %d", &x, &y); int fx = get(x), fy = get(y);//找堆顶 if (fx == fy) puts("-1");//若在同一个堆中输出-1 else { pop(fx), pop(fy);//删除堆顶 a[fx] >>= 1, a[fy] >>= 1; f[fx] = merge(fx, f[fx]), f[fy] = merge(fy, f[fy]);//将新值插入堆顶 fx = get(fx), fy = get(fy); printf("%d\n", a[merge(fx,fy)]);//输出堆顶，注意堆中存的是下标而不是数 } } } int main() { while (cin >> n) work(); return 0; } ```