---

题意回顾

我们有 $n$ 条线段 $[l_i, r_i]$。
一个线段集合是 复杂的，当且仅当它能被划分为若干个子集，使得：

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

换句话说，每个子集内部两两相交，不同子集之间两两不相交。
目标：从给定的 $n$ 条线段中选出一个最大的子集（记其大小为 $S$），使得这个子集是复杂的。

输出 $S$。

---

问题重述

设我们最终选出的子集有 $k$ 组，每组 $m$ 条线段，则 $S = k \cdot m$。
这 $k$ 组之间互不相交（因为不同组的线段不能相交），但组内任意两条都相交。

也就是说，每一组是一个 团（clique）在相交关系图中，且不同团之间无边。

---

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

如果固定每组的大小为 $m$，问题变成：
在 $n$ 条线段中，最多能选出多少个互不相交的团，每个团大小恰好为 $m$？

因为不同团之间不能有边，所以这些团是 边不交 的（即线段互不相交）。
而且同一个团内的所有线段必须两两相交，这意味着团内所有线段的交集非空。

性质

一个大小为 $m$ 的团，其交区间非空，等价于存在一个点 $x$，使得这 $m$ 条线段都包含 $x$。
所以我们可以把问题看作：找 $k$ 个互不相交的 $x$（每个 $x$ 对应一个团），每个 $x$ 覆盖恰好 $m$ 条线段。

更精确地说：
我们按 $r_i$ 排序，扫描时维护一个数据结构，标记哪些线段还未被分配。
当发现一个点 $p$ 被至少 $m$ 条未分配的线段覆盖时，我们就从中任意选 $m$ 条组成一个团，并移除它们。

---

算法实现（固定 $m$）

1. 将线段按 $r_i$ 升序排序，保证处理时右端点单调。
2. 初始化一个数组 $cnt[pos]$，表示当前未分配的线段中，覆盖点 $pos$ 的数量。
3. 遍历每条线段（按 $r$ 顺序）：
   • 把当前线段标记为“活跃”（未分配）。
   • 在 $[l_i, r_i]$ 区间上，$cnt$ 每个位置 $+1$。
   • 如果某个位置 $p$ 的 $cnt[p] \ge m$，说明可以形成一个团：
     选择覆盖 $p$ 的任意 $m$ 条线段（包括当前这条），移除它们（对应 $cnt$ 减 $1$），并增加 $k$。
4. 最终 $k$ 就是最多能形成的团数。

这个过程的难点在于：如何快速找到第一个 $cnt[p] \ge m$ 的位置？

优化

• 用线段树维护 $cnt$ 数组，区间加 $1$ 和查询最大值的位置。
• 找到后，需要找到覆盖 $p$ 的 $m$ 条线段并移除。
  移除意味着将这些线段从活跃状态删除，对 $cnt$ 的影响是：对于每条被移除的线段 $[l, r]$，$cnt$ 在 $[l, r]$ 上减 $1$。

但注意：移除的线段可能还未被遍历到（即它们的 $r$ 大于当前扫描的 $r$）。
实际上，我们可以在扫描时维护一个“已分配”的线段集合，但这样复杂度会高。

---

官方解法中的技巧

他们用一个二进制字符串维护“哪些线段是当前活跃的”，但更关键的是：
当找到一个点 $p$ 满足 $cnt[p] \ge m$ 时，这 $m$ 条线段一定包含当前正在处理的线段（按 $r$ 顺序）。
所以只需移除当前线段以及之前的一些未分配线段（按 $l$ 排序即可找到）。

实现细节：

• 维护一个 DSU（并查集），快速找到左边第一个未分配的线段。
• 移除时，更新覆盖计数（用区间减 $1$），但不需要显式维护 $cnt$ 数组，而是维护“后缀最大值”的变化。

最终复杂度：$O(n \alpha(n))$ 对于固定 $m$。

---

第二步：遍历所有可能的 $m$

我们需要最大化 $k \cdot m$。

注意到 $k \cdot m \le n$。
对于常数 $C$，要么 $m \le C$，要么 $k \le n/C$。

取 $C = \sqrt{n \log n}$，则：

• 当 $m \le C$ 时，枚举 $m = 1, 2, \dots, C$，每个 $m$ 用 $O(n \alpha(n))$ 计算最大 $k$，复杂度 $O(C \cdot n \alpha(n)) = O(n^{1.5} \log^{0.5} n \cdot \alpha(n))$。
• 当 $k \le n/C$ 时，枚举 $k = 1, 2, \dots, n/C$，每个 $k$ 用二分法找最大 $m$（因为 $m$ 越大 $k$ 越小），二分内调用 $O(n \alpha(n))$ 的判断，复杂度 $O((n/C) \cdot \log n \cdot n \alpha(n)) = O(n^{1.5} \log^{1.5} n \cdot \alpha(n))$。

取 $C = \sqrt{n \log n}$ 平衡两者，总复杂度 $O(n^{1.5} \sqrt{\log n} \cdot \alpha(n))$。

---

第三步：最终算法总结

1. 排序所有线段按 $r$ 升序。
2. 对于每个 $m$ 从 $1$ 到 $\sqrt{n \log n}$：
   • 用 DSU + 扫描法计算最大 $k$，更新答案 $ans = \max(ans, k \cdot m)$。
3. 对于每个 $k$ 从 $1$ 到 $n / \sqrt{n \log n}$：
   • 二分查找最大 $m$ 使得 $k$ 可行，更新答案。
4. 输出 $ans$。

---

时间复杂度

• 固定 $m$ 的扫描：$O(n \alpha(n))$，其中 $\alpha$ 是反阿克曼函数。
• 总复杂度 $O(n^{1.5} \sqrt{\log n} \cdot \alpha(n))$，足以通过困难版。

---

代码框架（伪代码）

def max_k(m, segments):
    # segments 按 r 排序
    # 维护 DSU 表示下一个未分配的线段
    # 扫描 r 递增
    # 每次发现一个点覆盖 >= m 条未分配线段时，移除 m 条
    return k

def solve():
    sort segments by r
    ans = 0
    C = int((n * log(n))**0.5)
    
    for m in 1..C:
        k = max_k(m)
        ans = max(ans, m * k)
    
    for k in 1..(n // C):
        # 二分 m
        lo, hi = 1, n // k
        while lo <= hi:
            mid = (lo+hi)//2
            if max_k(mid) >= k:
                lo = mid+1
            else:
                hi = mid-1
        ans = max(ans, k * hi)
    
    print(ans)

---