题目大意
给出n个人的权值，每次要求将两队人合成一堆，或者杀掉一堆人中的权值最小的那个人。问每次删除的人的权值是多少。
思路
就是可并堆，没了。我挑最简单的随机堆写的。
CODE;struct Heap{Heap *son[2];int val;Heap(int _):val(_) {son[0] = son[1] = NULL;}Heap() {}}*heap[MAX],mempool[MAX],*C = mempool + 1;Heap *Merge(Heap *x,Heap *y){if(x == NULL) return y;if(y == NULL) return x;if(x->val > y->val) swap(x,y);bool k = rand()&1;x->son[k] = Merge(x->son[k],y);return x;}int points,asks;int src[MAX];bool killed[MAX];char s[10];int father[MAX];int Find(int x){if(father[x] == x) return x;return father[x] = Find(father[x]);}int main(){srand(19970806);cin >> points;for(int i = 1; i <= points; ++i)father[i] = i;for(int x,i = 1; i <= points; ++i) {scanf(“%d”,&x);heap[i] = new (C++)Heap(x);}cin >> asks;for(int x,y,i = 1; i <= asks; ++i) {scanf(“%s”,s);if(s[0] == ‘M’) {scanf(“%d%d”,&x,&y);if(killed[x] || killed[y]) continue;int fx = Find(x),fy = Find(y);if(fx == fy) continue;father[fy] = fx;heap[fx] = Merge(heap[fx],heap[fy]);}else {scanf(“%d”,&x);if(killed[x]) {puts(“0”);continue;}int fx = Find(x);printf(“%d\n”,heap[fx]->val);killed[heap[fx] – mempool] = true;heap[fx] = Merge(heap[fx]->son[0],heap[fx]->son[1]);}}return 0;}
，悠然享受和大自然融合之乐。
