BZOJ 1455 罗马游戏 可并堆 -电脑资料

题目大意

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

BZOJ 1455 罗马游戏 可并堆

思路

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

CODE

<code class="language-cpp hljs ">#include<cstdio>#include<cstring>#include<iostream>#include #define MAX 1000010using 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;}</iostream></cstring></cstdio></code>