题意分析

题目描述的是纽曼（Newman）需要对大量的猫进行分组操作，并随时查询当前第k大的组的大小。具体来说：

1. 初始状态：有N只猫，每只猫初始时独立成组，组的大小为1。
2. 操作类型：
   • 合并操作（C=0）：将猫i和猫j所在的组合并。如果它们已经在同一组，则不做任何操作。
   • 查询操作（C=1）：查询当前所有组中第k大的组的大小。
3. 输出要求：对于每个查询操作，输出第k大的组的大小。

解题思路

为了高效处理合并和查询操作，我们需要以下数据结构和算法：

1. 并查集（Disjoint Set Union, DSU）：

   • 用于高效管理猫的分组，支持查找（Find）和合并（Union）操作。
   • 路径压缩优化：确保查找操作的时间复杂度接近O(1)。
   • 合并时更新组的大小。

2. 平衡二叉搜索树（Treap）：

   • 用于动态维护所有组的大小，支持插入、删除和查询第k大的元素。
   • Treap是一种随机化的二叉搜索树，结合了二叉搜索树和堆的性质，能够保证较高的操作效率（平均O(log n)）。
   • 需要支持以下操作：
     • 插入一个组的大小。
     • 删除一个组的大小。
     • 查询第k大的组的大小（注意是第k大，不是第k小）。

算法标签

• 并查集（DSU）：用于分组管理。
• 平衡二叉搜索树（Treap）：用于动态维护组的大小并支持查询。
• 路径压缩：优化并查集的查找操作。
• 随机化数据结构：Treap的随机化特性保证高效操作。

#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define sqz main
#define ll long long
#define reg register int
#define rep(i, a, b) for (reg i = a; i <= b; i++)
#define per(i, a, b) for (reg i = a; i >= b; i--)
#define travel(i, u) for (reg i = head[u]; i; i = edge[i].next)
const int INF = 1e9, N = 400000;
const double eps = 1e-6, phi = acos(-1.0);
ll mod(ll a, ll b) {if (a >= b || a < 0) a %= b; if (a < 0) a += b; return a;}
ll read(){ ll x = 0; int zf = 1; char ch; while (ch != '-' && (ch < '0' || ch > '9')) ch = getchar();
if (ch == '-') zf = -1, ch = getchar(); while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar(); return x * zf;}
void write(ll y) { if (y < 0) putchar('-'), y = -y; if (y > 9) write(y / 10); putchar(y % 10 + '0');}
int fa[N + 5], T[N + 5], point = 0, root;
int Find(int x)
{
    if (fa[x] != x) fa[x] = Find(fa[x]);
    return fa[x];
}
struct node
{
    int Val[N + 5], Level[N + 5], Size[N + 5], Son[2][N + 5], Num[N + 5];
    inline void up(int u)
    {
        Size[u] = Size[Son[0][u]] + Size[Son[1][u]] + Num[u];
    }
    inline void Newnode(int &u, int v)
    {
        u = ++point;
        Level[u] = rand(), Val[u] = v;
        Size[u] = Num[u] = 1, Son[0][u] = Son[1][u] = 0;
    }
    inline void Lturn(int &x)
    {
        int y = Son[1][x]; Son[1][x] = Son[0][y], Son[0][y] = x;
        Size[y] = Size[x]; up(x); x = y;
    }
    inline void Rturn(int &x)
    {
        int y = Son[0][x]; Son[0][x] = Son[1][y], Son[1][y] = x;
        Size[y] = Size[x]; up(x); x = y;
    }
 
    void Insert(int &u, int t)
    {
        if (u == 0)
        {
            Newnode(u, t);
            return;
        }
        Size[u]++;
        if (t == Val[u]) Num[u]++;
        else if (t > Val[u])
        {
            Insert(Son[0][u], t);
            if (Level[Son[0][u]] < Level[u]) Rturn(u);
        }
        else if (t < Val[u])
        {
            Insert(Son[1][u], t);
            if (Level[Son[1][u]] < Level[u]) Lturn(u);
        }
    }
    void Delete(int &u, int t)
    {
        if (!u) return;
        if (Val[u] == t)
        {
            if (Num[u] > 1)
            {
                Num[u]--, Size[u]--;
                return;
            }
            if (Son[0][u] * Son[1][u] == 0) u = Son[0][u] + Son[1][u];
            else if (Level[Son[0][u]] < Level[Son[1][u]]) Rturn(u), Delete(u, t);
            else Lturn(u), Delete(u, t);
        }
        else if (t > Val[u]) Size[u]--, Delete(Son[0][u], t);
        else Size[u]--, Delete(Son[1][u], t);
    }
 
    int Find_num(int u, int t)
    {
        if (!u) return 0;
        if (t <= Size[Son[0][u]]) return Find_num(Son[0][u], t);
        else if (t <= Size[Son[0][u]] + Num[u]) return u;
        else return Find_num(Son[1][u], t - Size[Son[0][u]] - Num[u]);
    }
}Treap;
int sqz()
{
    int n = read(), m = read();
    rep(i, 1, n) fa[i] = i, Treap.Insert(root, 1), T[i] = 1;
    while (m--)
    {
        int op = read();
        if (!op)
        {
            int x = Find(read()), y = Find(read());
            if (x != y)
            {
                Treap.Delete(root, T[x]), Treap.Delete(root, T[y]);
                fa[x] = y;
                T[y] += T[x];
                Treap.Insert(root, T[y]);
            }
        }
        else
        {
            int x = read();
            printf("%d\n", Treap.Val[Treap.Find_num(root, x)]);
        }
    }
}