题目链接

思路

左偏树的模板题，参考左偏树学习笔记

对于这道题我是用一个并查集维护出了哪些点是在同一棵树上，也可以直接log的往上跳寻找根节点

代码

#include<cstdio>

#include<iostream>

#include<cstdlib>

#include<cmath>

#include<ctime>

#include<bitset>

using namespace std;

typedef long long ll;

const int N = 100000 + 100;

inline char nc()

{

    static char buf[1<<14],*p1=buf,*p2=buf;

    return (p1==p2)&&(p2=(p1=buf)+fread(buf,1,1<<14,stdin),p1==p2)?EOF:*p1++;

}

inline int read()

{

    char c=nc();int x=0,f=1;

    while(c<'0'||c>'9'){if(c=='-')f=-1;c=nc();}

    while(c>='0'&&c<='9'){x=x*10+c-'0',c=nc();}

    return x*f;

}

int a[N],Pop[N],Col[N];

int n,m;

int ch[N][2],dist[N],fa[N];

int find(int x) {

    return x == fa[x] ? x : fa[x] = find(fa[x]);

}

void uni(int x,int y) {

    x = find(x),y = find(y);

    if(rand() & 1) fa[x] = y;

    else fa[y] = x;

}

int Merge(int x,int y) {

    if(x == 0 || y == 0) return x == 0 ? y : x;

    if(a[x] > a[y] || (a[x] == a[y] && x > y)) swap(x,y);

    ch[x][1] = Merge(ch[x][1],y);

    if(dist[ch[x][1]] > dist[ch[x][0]]) swap(ch[x][1],ch[x][0]);

    dist[x] = dist[ch[x][1]] + 1;

    return x;

}

inline void work1() {

    int x = read(),y = read();

    if(Pop[x] || Pop[y]) return;

    int k1 = Col[find(x)],k2 = Col[find(y)];

    if(k1 == k2) return;

    uni(x,y);

    int z = Merge(k1,k2);

    Col[find(x)] = z;

}

inline void work2() {

    int x = read();

    if(Pop[x]) {

        puts("-1");

        return;

    }

    int k = find(x);

    int y = Col[k];

    printf("%d\n",a[y]);

    Pop[y] = 1;

    int now = Merge(ch[y][0],ch[y][1]);

    Col[k] = now;

    ch[y][0] = ch[y][1] = 0;

}

int main() {

    n = read(), m = read();

    dist[0] = -1;

    for(int i = 1;i <= n; ++i) {

        a[i] = read();

        fa[i] = i;

        Col[i] = i;

    }

    while(m--) {

        int bz = read();

        if(bz == 1)  work1();

        if(bz == 2) work2();

    }

    return 0;

}

一言

目标不一定要说出来，去实现它就好。 ——屈屈，