原题链接： 二哥吃糖

题目描述

初始状态有 $n$ 个糖，每个糖单独一堆，进行 $m$ 次操作
- C a b 合并 a 所在的堆和 b 所在的堆
- D a 吃掉 a 所在的堆的所有糖
- Q k 询问糖的数量第 k 大的堆有多少块糖
$n \leq 5 × 10 ^ 5$
$m \leq 5 × 10 ^ 4$

输入样例

20 10
C 1 2
C 3 4
Q 2
Q 7
C 1 5
C 2 5
Q 1
D 5
Q 2
Q 1

输出样例

2
1
3
1
2

并查集 链表 平衡树

平衡树存每堆糖的数量，链表存每堆糖都有哪些糖

首先初始化并查集，往平衡树里放 $n$ 个 $1$，再整 $n$ 个链表，第 $i$ 个链表放个 $i$ 进去

合并操作 合并并查集，合并链表（记得更新 $tail$），平衡树删除之前两堆的数量，insert一个两堆之和

删除操作 找到这个糖所在的集合，给链表内所有元素打上删除标记，在平衡树中删除这堆糖的数量

询问操作 平衡树基本操作，根据 $rank$ 查找 $val$

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

C++ 代码

#include<cstdio>
#include<cstdlib>

const int N = 550010;

struct Node{
    int l, r;
    int val, key, sz;
}tr[N];

int root, tot;

int get_node(int val)
{
    int u = ++ tot;
    tr[u].val = val;
    tr[u].key = rand();
    tr[u].sz = 1;
    return u;
}

void pushup(int u)
{
    tr[u].sz = tr[tr[u].l].sz + tr[tr[u].r].sz + 1;
}

void split(int u, int val, int &x, int &y)
{
    if(!u)  x = y = 0;
    else
    {
        if(tr[u].val <= val)
        {
            x = u;
            split(tr[u].r, val, tr[u].r, y);
        }
        else
        {
            y = u;
            split(tr[u].l, val, x, tr[u].l);
        }
        pushup(u);
    }
}

int merge(int x, int y)
{
    if(!x or !y)  return x + y;
    if(tr[x].key > tr[y].key)
    {
        tr[x].r = merge(tr[x].r, y);
        pushup(x);
        return x;
    }
    else
    {
        tr[y].l = merge(x, tr[y].l);
        pushup(y);
        return y;
    }
}

int x, y, z;
void insert(int val)
{
    split(root, val, x, y);
    root = merge(merge(x, get_node(val)), y);
}

void dele(int val)
{
    split(root, val, x, y);
    split(x, val - 1, x, z);
    z = merge(tr[z].l, tr[z].r);
    root = merge(merge(x, z), y);
}

int get_val(int k)      //  第k大
{
    if(tr[root].sz < k)  return 0;

    int u = root;
    while(u)
    {
        if(tr[tr[u].r].sz + 1 == k)  break;
        if(tr[tr[u].r].sz >= k)  u = tr[u].r;
        else
        {
            k -= tr[tr[u].r].sz + 1;
            u = tr[u].l;
        }
    }
    return tr[u].val;
}

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

bool del[N];
int h[N], tail[N], e[N], ne[N], idx;

int main()
{
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i ++)
    {
        insert(1);
        p[i] = i,  sz[i] = 1;

        e[idx] = i;
        h[i] = tail[i] = idx;
        ne[idx ++] = -1;
    }

    while(m --)
    {
        char op[2];
        int a, b, k;
        scanf("%s", op);
        if(op[0] == 'C')
        {
            scanf("%d%d", &a, &b);
            int pa = find(a), pb = find(b);
            if(del[a] or del[b] or pa == pb)  continue;

            dele(sz[pa]);
            dele(sz[pb]);

            sz[pb] += sz[pa];
            p[pa] = pb;

            ne[tail[pb]] = h[pa];
            tail[pb] = tail[pa];

            insert(sz[pb]);
        }
        else if(op[0] == 'D')
        {
            scanf("%d", &a);
            if(del[a])  continue;
            int pa = find(a);
            for(int i = h[pa]; ~i; i = ne[i])  del[e[i]] = true;
            dele(sz[pa]);
        }
        else
        {
            scanf("%d", &k);
            printf("%d\n", get_val(k));
        }
    }
    return 0;
}