题目大意

给出n个人的权值，每次要求将两队人合成一堆，或者杀掉一堆人中的权值最小的那个人。问每次删除的人的权值是多少。

思路

就是可并堆，没了。我挑最简单的随机堆写的。

CODE

#include 
   
     #include 
    
      #include 
     
       #include 
      
        #define MAX 1000010 using namespace std; 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; }