题目重述（便于理解）

有 $n$ 条线段 $[l_i, r_i]$。

一个线段集合称为复杂集合，如果它可以划分成若干个子集，使得：

1. 所有子集的大小相同，设为 $m$；
2. 两条线段相交 $\iff$ 它们在同一个子集中。

这意味着：

• 每个子集内部，所有线段两两相交（形成一个团）；
• 不同子集之间，任意两条线段都不相交。

我们要求：从给定的 $n$ 条线段中，选出一个复杂集合，使得它的大小 $m \times k$ 最大（$k$ 是子集个数）。

---

核心观察

设：

• $m$ = 每个子集中的线段数
• $k$ = 子集个数

那么总大小 $= m \cdot k$。

关键：不同子集之间不能相交，所以子集是按“无交区间”排列的。每个子集内，所有线段必须相交于一个公共点（因为所有线段两两相交且都是闭区间）。

---

第一步：固定 $m$，求最大 $k$

我们定义：

$\text{max\_k}(m)$：在给定 $m$ 的情况下，最多能划分成多少个大小为 $m$ 的子集（每个子集内全相交，子集间不相交）。

如何计算 $\text{max\_k}(m)$？

算法思路（贪心 + 扫描线）

1. 将所有线段按右端点 $r_i$ 升序排序。
2. 维护一个数组 $cnt[x]$，表示位置 $x$ 当前被多少条“尚未被分配”的线段覆盖。
3. 从左到右扫描右端点：
   • 当某个点 $p$ 上的 $cnt[p] = m$ 时，这意味着当前有 $m$ 条线段都覆盖 $p$，且它们右端点已处理（按顺序保证了贪心最优），这 $m$ 条线段可以组成一个子集。
   • 将它们从考虑中移除（对应覆盖的点 $cnt$ 减 $m$，其实等价于把它们“清零”）。

更形式化地（标程方法）：

• 按 $r$ 排序后，用懒标记线段树维护每个点被覆盖的次数。
• 每次遇到 $r_i$，对区间 $[l_i, r_i]$ 加 $1$。
• 当某个位置的值达到 $m$ 时，收集这些线段形成一个子集，把它们覆盖的区间贡献清零。

这样扫描一遍，可以算出 $\text{max\_k}(m)$。

复杂度：对固定的 $m$，$O(n \log n)$。

---

第二步：固定 $k$，求最大 $m$

我们也可以反过来：

$\text{max\_m}(k)$：给定子集个数 $k$，每个子集最大可能的大小 $m$。

由于总线段数有限，$m \cdot k \le n$。

对于固定的 $k$，我们可以二分 $m$：

• 判断 $\text{max\_k}(m) \ge k$？
• 若能，则 $m$ 可行。

这样对每个 $k$ 二分，需要 $O(\log n)$ 次 $\text{max\_k}(m)$ 调用，每次 $O(n \log n)$，总 $O(n \log^2 n)$。

---

第三步：优化 —— 平衡 $m$ 和 $k$

我们目标是最大化 $m \cdot k$，且 $m \cdot k \le n$。

设 $C = \sqrt{n \log n}$。

策略：

• 如果 $m \le C$，枚举所有 $m = 1 \dots C$，计算 $\text{max\_k}(m)$，更新答案。
• 如果 $k \le \frac{n}{C}$，枚举所有 $k = 1 \dots \frac{n}{C}$，二分求 $\text{max\_m}(k)$，更新答案。

这样，总计算量：

• 枚举 $m$：$C$ 次 $\text{max\_k}(m)$，每次 $O(n \log n)$，总 $O(C \cdot n \log n) = O(n^{1.5} \log^{1.5} n)$。
• 枚举 $k$：$\frac{n}{C}$ 次二分，每次 $\text{max\_k}$ 是 $O(n \log n)$，总 $O(\frac{n}{C} \cdot n \log^2 n)$ 不对，等等，这里要小心。

更精确：

• 对每个 $k$，二分需要 $O(\log n)$ 次 $\text{max\_k}$。
• 所以总时间 $\frac{n}{C} \cdot \log n \cdot (n \log n) = \frac{n^2 \log^2 n}{C}$。
• 代入 $C = \sqrt{n \log n}$：$$\frac{n^2 \log^2 n}{\sqrt{n \log n}} = n^{1.5} \log^{1.5} n。 $$

所以两部分平衡，总复杂度 $O(n^{1.5} \log^{1.5} n)$，在 $n \le 2\times 10^4$ 时可以接受。

---

第四步：进一步优化 $\text{max\_k}(m)$

原题解提到可以用 DSU 优化到 $O(n \alpha(n))$ 而不是 $O(n \log n)$。

思路：

• 维护一个二进制串，初始全 $1$。
• 支持操作：
  1. 将位置 $p$ 设为 $0$；
  2. 找 $p$ 左边最近的 $1$。
• 用 DSU 维护连续 $0$ 段的父亲，可以 $O(\alpha(n))$ 完成。

这样 $\text{max\_k}(m)$ 的每次扫描变成 $O(n \alpha(n))$。

于是总复杂度：

$$O(n^{1.5} \alpha(n))$$

更优秀。

---

最终算法步骤

1. 读入 $n$ 条线段。
2. 预处理：将所有 $l_i, r_i$ 离散化，保证端点唯一且相对顺序不变。
3. 对 $m = 1 \dots \sqrt{n \log n}$：
   • 计算 $\text{max\_k}(m)$（用 DSU 优化版扫描）。
   • 更新答案 $\text{ans} = \max(\text{ans}, m \cdot \text{max\_k}(m))$。
4. 对 $k = 1 \dots \lfloor n / \sqrt{n \log n} \rfloor$：
   • 二分查找最大 $m$ 使得 $\text{max\_k}(m) \ge k$。
   • 更新答案。
5. 输出答案。

---

示例验证（题目样例）

以第二个样例：

n=5
l = 1 2 3 6 8
r = 5 4 7 9 10

排序后：

• $[1,5],[2,4],[3,7],[6,9],[8,10]$

手动检查：

• $m=2$：可以分成 $\{[1,5],[2,4]\}$ 和 $\{[6,9],[8,10]\}$，$k=2$，总大小 $4$。
• $m=3$：不够。
• $m=4$：不可能。

所以答案是 $4$。

---

总结

本题的核心是：

1. 理解复杂集合的结构 ⇒ 子集间无交，子集内全相交。
2. 固定 $m$ 贪心扫描求最大子集数。
3. 平衡枚举 $m$ 和 $k$ 达到 $O(n^{1.5} \log^{1.5} n)$。
4. 用 DSU 进一步优化到 $O(n^{1.5} \alpha(n))$。