Monkey King（左偏树）

洛谷传送门

每次给出要争吵的猴子a和b，用并查集判断如果他们是朋友输出1

如果不是，找出a，b在的堆的根A，B，分别合并A，B的左右孩子，再合并一下。

之后把A，B的数据更改一下：权值除以2，左右孩子设为0，再插入到堆中即可。

最后输出堆顶。

1 #include <iostream> 2 #include <cstdio> 3 4 using namespace std; 5 6 int n, m; 7 int f[100010], w[100010], d[100010], l[100010], r[100010]; 8 9 inline int merge(int x, int y) 10 19 20 inline int find(int x) 21 24 25 inline int pop(int x) 26 33 34 int main() 35 47 scanf("%d", &m); 48 for(i = 1; i <= m; i++) 49 58 x1 = pop(fx); 59 w[fx] /= 2; 60 x1 = merge(x1, fx); 61 y1 = pop(fy); 62 w[fy] /= 2; y1 = merge(y1, fy); 64 printf("%d\n", w[merge(x1, y1)]); 65 } 66 } 67 return 0; 68 }
View Code

上一篇：第k小整数（树状数组）

下一篇：[HDU3065]病毒持续侵袭中（AC自动机）

---

堆 左偏树