一个堆和一个并查集对应,并且满足并查集中所有没有死的人等于堆中的人
/**************************************************************
Problem: 1455
User: idy002
Language: C++
Result: Accepted
Time:2688 ms
Memory:32336 kb
****************************************************************/ #include <cstdio>
#define N 1000010 struct Node {
int u, w, s;
Node *ls, *rs;
void update() {
s = ;
if( ls ) s += ls->s;
if( rs ) s += rs->s;
}
}pool[N], *tail=pool, *root[N]; int n, m;
int fat[N], die[N]; int find( int a ) {
return a==fat[a] ? a : fat[a]=find(fat[a]);
}
Node *newnode( int u, int w ) {
Node *nd = ++tail;
nd->u = u;
nd->w = w;
nd->ls = nd->rs = ;
return nd;
}
Node *smerge( Node *na, Node *nb ) {
if( !na && !nb ) return ;
if( !na ) return nb;
if( !nb ) return na;
if( na->w < nb->w ) {
na->rs = smerge( na->rs, nb );
na->update();
return na;
} else {
nb->rs = smerge( nb->rs, na );
nb->update();
return nb;
}
}
int main() {
scanf( "%d", &n );
for( int i=,w; i<=n; i++ ) {
scanf( "%d", &w );
root[i] = newnode(i,w);
fat[i] = i;
}
scanf( "%d", &m );
for( int i=,u,v; i<=m; i++ ) {
char ch[];
scanf( "%s", ch );
if( ch[]=='M' ) {
scanf( "%d%d", &u, &v );
if( die[u] || die[v] ) continue;
int fu = find(u);
int fv = find(v);
if( fu==fv ) continue;
fat[fu] = fv;
root[fv] = smerge( root[fu], root[fv] );
} else {
scanf( "%d", &u );
if( die[u] ) {
printf( "0\n" );
continue;
}
int fu = find(u);
int v = root[fu]->u;
printf( "%d\n", root[fu]->w );
die[v] = true;
root[fu] = smerge( root[fu]->ls, root[fu]->rs );
}
}
}