题目描述

给定 $n$ 个数，起初每个数属于一个集合，进行 $m$ 次操作

操作1：把第 $x$ 个数所在的集合和第 $y$ 个数所在的集合合并（如果 $x$ 或 $y$ 已被删除那么无事发生）
操作2：把第 $x$ 个数所在的集合的最小的数输出，并删除最小数（如果有多个最小数，删除下标最小的那个，如果 $x$ 已被删除，那么输出 $-1$）

$n, m \leq 10^5$

输入样例

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

输出样例

1
2

线段树合并

似乎所有的左偏树题目都可以用线段树合并来做 可能这就是时代的眼泪吧

要区别不同下标的数，在离散化时把下标作为第二关键字排序即可

时间复杂度 $O((n + m)logn)$

C++ 代码

#include<cstdio>
#include<algorithm>
#include<vector>

#define x first
#define y second

using namespace std;

typedef pair<int, int> PII;

const int N = 1e5 + 10;

int p[N];
int find(int x)
{
    if(p[x] != x)  p[x] = find(p[x]);
    return p[x];
}

int a[N];
bool dele[N];

vector<PII> v;
int find(PII x)
{
    return lower_bound(v.begin(), v.end(), x) - v.begin();
}

struct Node{
    int l, r;
    int sz;
}tr[N * 18];

int root[N], tot;

int e[N], ne[N], idx;

void insert(int &u, int l, int r, int x)
{
    if(!u)  u = ++ tot;

    tr[u].sz ++;
    if(l == r)  return;
    int mid = l + r >> 1;
    if(x <= mid)  insert(tr[u].l, l, mid, x);
    else  insert(tr[u].r, mid + 1, r, x);
}

int query(int u, int l, int r)
{
    tr[u].sz --;
    if(l == r)
    {
        dele[v[l].y] = true;
        return v[l].x;
    }
    int mid = l + r >> 1;
    if(tr[tr[u].l].sz)  return query(tr[u].l, l, mid);
    return query(tr[u].r, mid + 1, r);
}

int merge(int x, int y, int l, int r)
{
    if(!x or !y)  return x | y;

    int u = x;
    tr[u].sz = tr[x].sz + tr[y].sz;
    if(l == r)  return u;

    int mid = l + r >> 1;
    if(tr[x].l or tr[y].l)  tr[u].l = merge(tr[x].l, tr[y].l, l, mid);
    if(tr[x].r or tr[y].r)  tr[u].r = merge(tr[x].r, tr[y].r, mid + 1, r);
    return u;
}

int main()
{
    int n, m;
    scanf("%d%d", &n, &m);

    for(int i = 1; i <= n; i ++)  scanf("%d", &a[i]),  p[i] = i,  v.push_back({a[i], i});

    sort(v.begin(), v.end());

    for(int i = 1; i <= n; i ++)  insert(root[i], 0, v.size() - 1, find({a[i], i}));

    while(m --)
    {
        int op, x, y;
        scanf("%d%d", &op, &x);
        if(op == 1)
        {
            scanf("%d", &y);
            if(dele[x] or dele[y])  continue;
            x = find(x), y = find(y);
            p[x] = y;
            root[y] = merge(root[x], root[y], 0, v.size() - 1);
        }
        else
        {
            if(dele[x])
            {
                puts("-1");
                continue;
            }
            x = find(x);
            printf("%d\n", query(root[x], 0, v.size() - 1));
        }
    }
    return 0;
}