Luogu 题库
U720134 嘎鱼集团
PAGE 01 / 06
Luogu U720134 · Problem Statement

📄 第一页：题目背景与任务全貌

👑 题目背景（洛谷 U720134）： 嘎鱼星球的天子 ql 闲着无聊，命令其子民（简称 wkb）组建集团。给定 $n$ 个子民（编号 $1 \sim n$），每个人初始自成一个集团，第 $i$ 个人的初始嘎鱼值为 $a_i$。

📌 四大约束操作（3 个在线指令 + 1 个最终问答）

操作类型 操作指令 具体要求
操作 1 (合体) 1 u v 将 $u$ 和 $v$ 所在的嘎鱼集团合并。若已同属一个集团则忽略本次操作。
操作 2 (查人数) 2 u 查询 $u$ 所在嘎鱼集团中包含的子民总人数。
操作 3 (查极值) 3 u 查询 $u$ 所在嘎鱼集团中嘎鱼值的最大值 $\max(a_i)$。
最终问答 (队伍) 所有操作结束后 计算出 ql 最多能挑选出多长的、不含同集团成员的连续游行队伍？
Example Simulation

🔍 第二页：样例推导与互动模拟

📥 洛谷输入样例

5 6
3 8 2 10 5
1 1 2
3 1
2 1
1 4 5
3 4
2 5

📤 期望输出与解释

8    # 3 1: 查询 1 所在集团最大值 -> max(3, 8) = 8
2    # 2 1: 查询 1 所在集团总人数 -> {1, 2} 共 2 人
10   # 3 4: 查询 4 所在集团最大值 -> max(10, 5) = 10
2    # 2 5: 查询 5 所在集团总人数 -> {4, 5} 共 2 人
3    # 最终最长无重复集团连续队伍长度为 3

🎮 最终队伍分布演算（点击互动观察连续区间）

全部合并后，5 个人的集团归属为：wkb[1]: G1, wkb[2]: G1, wkb[3]: G3, wkb[4]: G4, wkb[5]: G4

wkb 1G1
wkb 2G1
wkb 3G3
wkb 4G4
wkb 5G4

Hints & Thinking

💡 第三页：破题提示与思考切入点

⚡ 关键提示 1：动态连通性与动态属性维护

题目中的操作只有“合并集团”，**从不拆分集团**。这是最标准的等价类合并场景。除了维护两个元素是否在同一集团，我们还需要快速查询：

  • 该集团的大小（总人数）
  • 该集团的最大嘎鱼值（极值）

思考：普通图遍历合并耗时太高，什么数据结构可以在几乎 $\mathcal{O}(1)$ 的时间内完成合并并更新这些属性？ $\to$ 并查集 (Union-Find)。

⚡ 关键提示 2：最终队伍的转化

“挑选最长的、不含同集团成员的连续游行队伍” $\Longleftrightarrow$ “在数组中找到最长连续子区间 $[L, R]$，使得区间内各元素的集团 ID 互不相同”。

  • 如果用两层循环暴力枚举区间 $[L, R]$，复杂度为 $\mathcal{O}(N^2)$。当 $N = 2 \times 10^5$ 时，$N^2 = 4 \times 10^{10}$，必然严重超时 (TLE)！
  • 由于区间的合法性具备单调性（随着右端点增加，重复元素出现时只需右移左端点），可以运用滑动窗口（双指针）在 $\mathcal{O}(N)$ 线性时间内完美解决！
Core Algorithms

🛠️ 第四页：所需核心知识点与复杂度分析

1. 带附加信息的并查集 (DSU)

通过路径压缩技术，保证树的高度极低：

  • fa[x]：记录节点 $x$ 的父节点。
  • sz[root]：只在根节点维护该连通块的子民总数。
  • mx[root]：只在根节点维护该连通块的最大嘎鱼值。
  • 合并两个根 $fu, fv$ 时：
    sz[fu] += sz[fv];
    mx[fu] = max(mx[fu], mx[fv]);

2. 滑动窗口 / 双指针算法

维护一个不含重复集团的动态窗口 $[L, R]$：

  • 用数组 cnt[gid] 记录当前窗口内每个集团出现的次数。
  • 右指针 $R$ 从 $1$ 遍历到 $n$，加入元素。
  • 若当前元素所属集团 cnt[gid] > 0（发生冲突），则不断右移左指针 $L$，直到冲突消除。
  • 每次更新答案：$\text{ans} = \max(\text{ans}, R - L + 1)$。

📊 算法时空复杂度分析

  • 时间复杂度： 并查集单次操作为反阿克曼函数 $\mathcal{O}(\alpha(N)) \approx \mathcal{O}(1)$；双指针左右端点各遍历一次，为 $\mathcal{O}(N)$。总时间复杂度为 $\mathcal{O}(N + M \alpha(N))$，在洛谷 $2 \times 10^5$ 满额数据规模下仅需约 40ms！
  • 空间复杂度： 几个大小为 $2 \times 10^5$ 的数组（fa, sz, mx, root_id, cnt），空间约为 6MB，远低于洛谷题目内存限制。
Implementation Details

💻 第五页：核心关键操作实现与代码拆解

1️⃣ 路径压缩的 Find 与 带权 Merge

// 路径压缩：查找根节点的同时将沿途所有节点直接挂载到根上
int find(int x) {
    return fa[x] == x ? x : fa[x] = find(fa[x]);
}

// 集团合并操作
void merge(int u, int v) {
    int fu = find(u), fv = find(v);
    if (fu != fv) {
        fa[fv] = fu;                      // fv 认 fu 为新祖先
        sz[fu] += sz[fv];                 // 累加两集团的总人数
        mx[fu] = max(mx[fu], mx[fv]);     // 更新合并后集团的最大嘎鱼值
    }
}

2️⃣ 最终连续队伍的双指针算法实现

// 先预处理出每个人最终所属的代表元（根节点）
for (int i = 1; i <= n; ++i) {
    root_id[i] = find(i);
}

// 经典滑动窗口双指针
int ans = 0, l = 1;
for (int r = 1; r <= n; ++r) {
    int g = root_id[r];
    while (cnt[g] > 0) {       // 窗口内已存在同集团成员，收缩左边界
        cnt[root_id[l]]--;
        l++;
    }
    cnt[g]++;                  // 将当前集团计入窗口
    ans = max(ans, r - l + 1); // 实时更新无冲突最大队伍长度
}
Full Source Code

🏆 第六页：完整标准 AC 源码与避坑总结

#include 
using namespace std;

// 洛谷 U720134 嘎鱼集团 - 标准 AC 代码
const int N = 200005;
int fa[N], sz[N], mx[N];
int root_id[N], cnt[N];

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

void merge(int u, int v) {
    int fu = find(u), fv = find(v);
    if (fu != fv) {
        fa[fv] = fu;
        sz[fu] += sz[fv];
        mx[fu] = max(mx[fu], mx[fv]);
    }
}

int main() {
    // 极致 IO 加速
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    if (!(cin >> n >> m)) return 0;

    for (int i = 1; i <= n; ++i) {
        fa[i] = i;
        sz[i] = 1;
        cin >> mx[i];
    }

    while (m--) {
        int op, u, v;
        cin >> op;
        if (op == 1) {
            cin >> u >> v;
            merge(u, v);
        } else if (op == 2) {
            cin >> u;
            cout << sz[find(u)] << "\n";
        } else if (op == 3) {
            cin >> u;
            cout << mx[find(u)] << "\n";
        }
    }

    // 预处理最终集团归属
    for (int i = 1; i <= n; ++i) root_id[i] = find(i);

    // 双指针统计最长连续无重复队伍
    int ans = 0, l = 1;
    for (int r = 1; r <= n; ++r) {
        int g = root_id[r];
        while (cnt[g] > 0) {
            cnt[root_id[l]]--;
            l++;
        }
        cnt[g]++;
        ans = max(ans, r - l + 1);
    }

    cout << ans << "\n";
    return 0;
}

⚠️ 考场避坑核心总结

  • 查询必须查 find(u)：输出 sz 和 mx 时不能写 sz[u]，因为只有根节点保存了最新的全局汇总信息。
  • 双指针前统一 find(i)：必须先完整获取各元素的根节点 ID，避免浅层父节点未压缩导致判断失误。
💡 支持键盘 ← → 方向键快速翻页