洛谷传送门
每次给出要争吵的猴子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
上一篇：求逆序对（树状数组）
下一篇：[USACO11NOV]牛的障碍Cow Steeplechase（匈牙利算法）
堆 左偏树
