NOIP模板复习 _ 可并堆(Mergeable_heap) – [模板]

#include 
#include 
const int N = 100001;
int ls[N], rs[N], dis[N], val[N], fa[N], cnt;
char buf[100000], *p1, *p2;
#define nc() (p1==p2&&(p2=(p1=buf)+fread(buf, 1, 100000, stdin), p1==p2)?EOF:*p1++)
inline char gc() {
    char ch = nc();
    while(isspace(ch)) ch = nc();
    return ch;
}
inline int rd() {
    int x = 0; char ch = nc();
    while(!isdigit(ch)) ch = nc();
    while( isdigit(ch)) x = (((x<<2)+x)<<1)+(ch^48), ch = nc();
    return x;
}
int find(int x) {return fa[x]==x?x:fa[x]=find(fa[x]);}
int merge(int x, int y) {
    if(!x || !y) return x+y;
    if(val[x] > val[y]) std :: swap(x, y);
    rs[x] = merge(rs[x], y);
    if(dis[ls[x]] < dis[rs[x]]) std :: swap(ls[x], rs[x]);
    dis[x] = dis[rs[x]]+1;
    return x;
}
int main() {
    int n, m; scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i ++ ) {
        fa[i] = i;
        val[i] = rd();
    }
    for(int i = 1; i <= m; i ++ ) {
        int opt = rd(), x = rd();
        if(opt == 1) {
            int y = rd();
            if(val[x] == -1 || val[y] == -1) continue;
            x = find(x), y = find(y);
            if(x != y) fa[x] = fa[y] = merge(x, y);
        }
        else {
            if(val[x] == -1) {puts("-1"); continue;}
            int dx = find(x); printf("%d\n", val[dx]);
            fa[dx] = fa[ls[dx]] = fa[rs[dx]] = merge(ls[dx], rs[dx]);
            val[dx] = -1;
        }
    }
}

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注