左偏树

朴灿烈づ我的快乐病毒、 2024-04-18 19:51 68阅读 0赞

### 题目描述 ###

如题，一开始有N个小根堆，每个堆包含且仅包含一个数。接下来需要支持两种操作：

操作1： 1 x y 将第x个数和第y个数所在的小根堆合并（若第x或第y个数已经被删除或第x和第y个数在用一个堆内，则无视此操作）

操作2： 2 x 输出第x个数所在的堆最小数，并将其删除（若第x个数已经被删除，则输出-1并无视删除操作）

### 输入格式 ###

第一行包含两个正整数N、M，分别表示一开始小根堆的个数和接下来操作的个数。

第二行包含N个正整数，其中第i个正整数表示第i个小根堆初始时包含且仅包含的数。

接下来M行每行2个或3个正整数，表示一条操作，格式如下：

操作1 ： 1 x y

操作2 ： 2 x

### 输出格式 ###

输出包含若干行整数，分别依次对应每一个操作2所得的结果。

### 输入输出样例 ###

**输入 \#1**复制

5 5
    1 5 4 2 3
    1 1 5
    1 2 5
    2 2
    1 4 2
    2 2

**输出 \#1**复制

1
    2

#include<bits/stdc++.h>
    using namespace std;
    const int M = 1e5+50;
    int inline read()
    {
        int x=0,f=1;char ch=getchar();
        while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
        while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
        return x*f;
    }
    void swap(int &x,int &y){int t=x;x=y;y=t;}
    int ch[M][2],v[M],d[M],f[M],n,m;
    int rt(int x){//此处没有路径压缩，会导致时间效率底下，看情况使用并查集维护
        while(f[x])x=f[x];
        return x;
    }
    int merge(int x,int y)
    {
        if (x==0 || y==0)
            return x+y;
        if (v[x]>v[y] || (v[x]==v[y] && x>y))
            swap(x,y);
        ch[x][1]=merge(ch[x][1],y);
        f[ch[x][1]]=x;
        if (d[ch[x][0]]<d[ch[x][1]])
            swap(ch[x][0],ch[x][1]);
        d[x]=d[ch[x][1]]+1;
        return x;
    }
    int main(){
        scanf("%d%d",&n,&m);
        d[0]=-1;
        for(int i=1;i<=n;i++) v[i] = read();
        for(int fx,fy,op,x,y,i=1;i<=m;i++){
            op=read();
            if(op==1){
                x=read();y=read();
                if(v[x]==-1||v[y]==-1||x==y)continue;
                fx=rt(x);fy=rt(y);
                merge(fx,fy);
            }else{
                x=read();
                if(v[x]==-1)puts("-1");
                else {
                    y=rt(x);
                    printf("%d\n",v[y]);
    
                    v[y]=-1;
                    f[ch[y][0]]=f[ch[y][1]]=0;
                    merge(ch[y][0],ch[y][1]);
                }
            }
        }
        return 0;
    }