CF D2. Come Be My Friend, Don’t Be So Scared (Hard Version) 详细题解

一、题意回顾与初步转化

有 $n$ 个藏身之处排成一排，编号 $1 \sim n$ 。目前已安装了 $m$ 个探测器，第 $i$ 个探测器覆盖区间 $[l_i, r_i]$ 。当一个人藏在位置 $x$ 时，所有包含 $x$ 的探测器都会报警。
我们需要再安装最少数量的探测器（每个也是一个区间 $[u_j, v_j]$ ），使得无论藏在哪个位置，所有探测器的报警状态组合都是独一无二的。

1. 什么叫“无法区分”？

在未加新探测器之前，对于两个不同的位置 $x$ 和 $y$ ，如果每一个已有的探测器要么同时覆盖 $x$ 和 $y$ ，要么同时不覆盖 $x$ 和 $y$ ，那么无论藏在 $x$ 还是 $y$ ，已有探测器的反馈都完全一致，我们就称 $x$ 和 $y$ 目前处于同一个等价类（同色）。

2. 用“异或哈希”快速划分等价类

如何快速找出哪些位置处于同一个等价类？我们可以使用异或哈希（XOR Hashing）：

将位置从 $1 \sim n$ 平移为 $0 \sim n-1$ ，此时原来的闭区间 $[l, r]$ 变成了左闭右开区间 $[l-1, r)$ 。
为每个已有的探测器随机生成一个 64 位无符号整数 $w \in [0, 2^{64}-1]$ ，将区间 $[l-1, r)$ 内的所有位置异或上 $w$ （可通过差分数组 + 前缀异或和在 $O(n + m)$ 时间内完成）。
最终每个位置 $i$ 会得到一个哈希值 $d[i]$ 。由于 64 位随机数发生哈希冲突的概率极低（约为 $\frac{n^2}{2^{64}} \approx 10^{-9}$ ），我们可以认为： $d[x] = d[y]$ 当且仅当位置 $x$ 和位置 $y$ 目前无法被区分。

二、核心转化：从“选区间”到“环上选切分点”

1. 探测器的本质是“环上的两个切分点”

把 $n$ 个位置 $0, 1, \dots, n-1$ 顺时针排在一个环上。相邻两个位置之间有一个“间隙”：

间隙 $1$ 在位置 $0$ 和 $1$ 之间；
间隙 $2$ 在位置 $1$ 和 $2$ 之间；
……
间隙 $i$ 在位置 $i-1$ 和 $i$ 之间（ $1 \le i \le n-1$ ）；
间隙 $n$ 在位置 $n-1$ 和 $0$ 之间（即环的接缝处）。

现在考虑任意一个区间探测器（0-indexed 下为 $[l, r)$ ，满足 $0 \le l < r \le n$ ；对应 1-indexed 输出为 $[l+1, r]$ ）：

它的左边界切开了位置 $l-1$ 和 $l$ （对应间隙 $l$ ，若 $l=0$ 则对应间隙 $n$ ）；
它的右边界切开了位置 $r-1$ 和 $r$ （对应间隙 $r$ ，若 $r=n$ 则对应间隙 $n$ ）。

因此，每放置一个探测器，本质上就是在环上的 $n$ 个间隙 $\{1, 2, \dots, n\}$ 中选择了两个不同的切分点 $l$ 和 $r$ （ $1 \le l < r \le n$ ）。

2. 神奇的“交叉配对构造法”

假设我们在环上选出了 $2k$ 个切分点： $1 \le e_1 < e_2 < \dots < e_{2k} \le n$ 。
我们采用交叉配对（Cross-Pairing）的方式来构造 $k$ 个新探测器：

第 $j$ 个探测器（ $1 \le j \le k$ ）的左右切分点设为 $(e_j, e_{j+k})$ ，即覆盖 0-indexed 区间 $[e_j, e_{j+k})$ （对应题目 1-indexed 闭区间 $[e_j + 1, e_{j+k}]$ ）。

这 $2k$ 个切分点把环切成了 $2k$ 段弧（其中跨越环接缝的 $[0, e_1) \cup [e_{2k}, n)$ 属于同一段弧，因为它不被任何新探测器覆盖）。
让我们看看从 $e_1$ 顺时针走到 $e_{2k}$ 的过程中，每一段弧被哪些新探测器覆盖：

弧 $[e_1, e_2)$ ：被探测器 $\{1\}$ 覆盖；
弧 $[e_2, e_3)$ ：被探测器 $\{1, 2\}$ 覆盖；
$\dots$
弧 $[e_k, e_{k+1})$ ：被探测器 $\{1, 2, \dots, k\}$ 覆盖；
弧 $[e_{k+1}, e_{k+2})$ ：探测器 $1$ 结束，被 $\{2, 3, \dots, k\}$ 覆盖；
$\dots$
弧 $[e_{2k}, e_1 + n)$ ：不被任何新探测器覆盖，集合为 $\varnothing$ 。

惊人的结论出现了：
前 $k$ 步每一步都新加入一个探测器，后 $k$ 步每一步都移除一个最早加入的探测器！
这意味着：被这 $2k$ 个切分点切出来的 $2k$ 段环上弧，它们各自对应的新探测器报警集合是两两完全不同的！

3. 等价条件：同色相邻点之间必须有切分点

既然新切出来的每一段弧都拥有独一无二的报警状态，那么要让原本处于同一个等价类（同色）的集合 $S = \{i_1, i_2, \dots, i_c\}$ （ $|S| \ge 2$ ）中的所有点两两可区分，充要条件就是：
集合 $S$ 中的任意两个点，都不能落在同一段弧内！

把这个条件翻译到环上：将 $S$ 中的点按顺时针排序为 $0 \le i_1 < i_2 < \dots < i_c < n$ ，它们在环上构成了 $c$ 个相邻同色区间：
$[i_1, i_2),\ [i_2, i_3),\ \dots,\ [i_{c-1}, i_c),\ [i_c, i_1 + n)$
要使任意两点不落在同一段弧内，当且仅当上述每一个环上相邻同色区间 $(l, r]$ 内部，都至少包含一个我们选出的切分点 $e$ （即满足 $l < e \le r$ ，若跨过环边界则是 $l < e + n \le r$ ）！

三、几何性质：为什么极小同色区间两两不相交？

经过上面的转化，问题变成了：

在环上有若干个限制区间 $[l, r)$ （每个位置 $l$ 顺时针方向找到下一个同色位置 $r$ ，若 $r < l + n$ 则产生一个限制区间 $[l, r)$ ），要求在 $\{1, 2, \dots, n\}$ 中选出最少的切分点，使得每个限制区间 $(l, r]$ 内至少有一个切分点。

如果这是一个普通的环形区间选点问题，通常需要排序后用贪心 + 倍增来做。但 jiangly 的代码中只求了一个后缀最小值，然后直接把所有满足 f[i] != f[i+1] 的左端点旁边的点 i + 1 选了出来！为什么这样可以？

这就用到了本题隐藏最深的一个区间几何性质。

1. 什么是“极小限制区间”？

如果限制区间 $A = [l_1, r_1)$ 完全包含了另一个限制区间 $B = [l_2, r_2)$ （即 $l_1 \le l_2 < r_2 \le r_1$ ），那么只要我们在 $B$ 中选了切分点，就一定自动满足了 $A$ 。所以 $A$ 是冗余的，我们只需要关心那些不包含任何其他限制区间的“极小限制区间”。

如何筛出所有极小限制区间？
设 $f[i]$ 表示以 $i$ 为左端点的限制区间右端点（若无则为 $2n$ ）。我们从右往左更新：
$f[i] = \min(f[i], f[i+1])$
（因为是环，绕环更新两圈）。更新完后， $f[i]$ 表示所有左端点 $\ge i$ 的限制区间中，最靠左的右端点。
此时，如果某个位置 $i$ 满足 $f[i] < f[i+1]$ （且 $f[i] < i + n$ ），就说明没有更靠右的区间终点落在 $f[i]$ 之前或等于 $f[i]$ ，即 $[i, f[i])$ 就是一个极小限制区间！

2. 定理：所有的极小限制区间在环上两两不相交！

证明：
假设存在两个极小限制区间在环上相交但不包含，即存在四个位置沿着环顺时针依次为：
$i_1 < i_2 < r_1 < r_2$
其中 $(i_1, r_1)$ 同色（哈希值相同）， $(i_2, r_2)$ 同色，且这两组的颜色不同（若颜色相同，则 $i_1$ 的下一个同色点不可能跨过 $i_2$ 到 $r_1$ ）。
既然 $(i_1, r_1)$ 和 $(i_2, r_2)$ 颜色不同，说明必然存在至少一个已有的探测器，它覆盖了其中一组（比如覆盖了 $i_1$ 和 $r_1$ ），但没有覆盖另一组（没有覆盖 $i_2$ 和 $r_2$ ）。
但是，沿着环顺时针走一圈： $i_1 \text{ (覆盖)} \to i_2 \text{ (不覆盖)} \to r_1 \text{ (覆盖)} \to r_2 \text{ (不覆盖)} \to i_1 \text{ (覆盖)}$ 。
你会发现，这个探测器的覆盖状态在环上切换了 $4$ 次！
然而，任何一个区间探测器 $[l, r]$ 在环上只有 $2$ 个端点，状态最多只能切换 $2$ 次！矛盾！

3. 直接得出最优切分方案

既然所有的极小限制区间 $[i, f[i])$ 在环上是两两完全不相交的（即前一个的右端点 $\le$ 后一个的左端点）：

如果有 $c$ 个极小限制区间，由于它们互不相交，任何 $1$ 个切分点最多只能满足其中 $1$ 个极小区间，因此至少需要 $c$ 个切分点。
反过来，我们在每个极小限制区间 $[i, f[i])$ 的最左侧直接选切分点 $i + 1$ （由于 $f[i] \ge i + 1$ ，切分点 $i + 1$ 一定落在该极小区间 $(i, f[i]]$ 内）。这 $c$ 个切分点不仅满足了全部 $c$ 个极小区间，而且因为所有非极小区间都至少包含一个极小区间，所以所有限制区间都被完美切开！

四、奇偶性补齐与边界处理

假设我们一共找出了 $c$ 个极小限制区间（即代码中的 ends.size() == c）：

每个新探测器提供 $2$ 个切分点，因此最少需要 $\lceil c / 2 \rceil$ 个探测器。
如果 $c$ 是偶数：直接将前一半 ends[i] 和后一半 ends[i + c / 2] 配对即可。
如果 $c$ 是奇数：
- 首先， $c$ 绝不可能等于 $1$ ！
  因为如果 $c = 1$ ，说明整个环上只有两个点同色、且只形成了一个方向的小于 $n$ 的区间，但两个同色点 $x, y$ 在环上会把环分成两段： $[x, y)$ 和 $[y, x+n)$ ，这两段长度之和为 $n$ ，不可能只有一段 $< n$ ！所以只要有未区分的点对，极小区间的数量必然满足 $c \ge 2$ 。
- 当 $c \ge 3$ 且为奇数时，我们需要 $\frac{c+1}{2}$ 个探测器，还差 $1$ 个切分点凑成偶数。
- 代码中非常巧妙地执行了 ends.push_back(ends.back());，也就是把最后一个切分点重复放了一次。
- 重复放最后一个切分点会导致最后一个探测器退化成空区间吗？不会！因为此时数组长度变为 $2k = c + 1 \ge 4$ ，即 $k \ge 2$ 。最后一个探测器配对的是下标 k - 1 和 2k - 1，而重复的两个元素在下标 2k - 2 和 2k - 1。由于 $k \ge 2 \implies k - 1 < 2k - 2$ ，所以 ends[k - 1] 严格小于 ends[2k - 1]，构造出的区间依然是合法的非空区间！且多出来的这个相同右端点丝毫不影响前面 $c$ 个切分点把所有极小区间切开的性质。

五、代码逐行详细注释（jiangly 原版代码）

#include <bits/stdc++.h>

using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned;

using u128 = unsigned __int128;
using i128 = __int128;

namespace rgs = std::ranges;

// 64位随机数生成器，用于异或哈希
std::mt19937_64 rng(std::chrono::steady_clock::now().time_since_epoch().count());

void solve() {
    int n, m;
    std::cin >> n >> m;
    
    // d[i] 用于差分计算每个位置被覆盖的探测器集合的异或哈希值
    std::vector<u64> d(n);
    
    for (int i = 0; i < m; i++) {
        int l, r;
        std::cin >> l >> r;
        l--; // 转为 0-indexed 左闭右开区间 [l, r)
        u64 w = rng();
        d[l] ^= w;
        if (r < n) {
            d[r] ^= w;
        }
    }
    
    // 求前缀异或和，此时 d[i] 即为位置 i 的状态哈希值
    for (int i = 1; i < n; i++) {
        d[i] ^= d[i - 1];
    }
    
    // 将所有位置按 (哈希值, 下标) 排序，方便找出同色相邻点
    std::vector<std::pair<u64, int>> p;
    for (int i = 0; i < n; i++) {
        p.emplace_back(d[i], i);
    }
    rgs::sort(p);
    
    // f[l] 记录从位置 l 顺时针出发，下一个同色点的位置 r（若跨过环边界则 +n）
    std::vector<int> f(n, 2 * n);
    for (int i = 0, j = 0; i < n; i++) {
        // 同一个等价类中，顺时针相邻的两个点 p[i-1].second 和 p[i].second
        if (i != j) {
            int l = p[i - 1].second;
            int r = p[i].second;
            f[l] = std::min(f[l], r);
        }
        // 到达当前等价类的末尾，处理最后一个点顺时针绕过环边界回到第一个点 p[j].second 的情况
        if (i == n - 1 || p[i + 1].first != p[i].first) {
            int l = p[i].second;
            int r = p[j].second + n;
            // 注意：如果该等价类只有 1 个点（i == j），此时 r = l + n，后面会过滤掉长度 >= n 的区间
            f[l] = std::min(f[l], r);
            j = i + 1; // 移动到下一个等价类的起点
        }
    }
    
    // 在环上求后缀最小值：f[i] = min(f[i], f[i + 1])
    // 绕环跑 2 圈即可确保环形依赖完全收敛
    for (int t = 0; t < 2; t++) {
        for (int i = n - 2; i >= 0; i--) {
            f[i] = std::min(f[i], f[i + 1]);
        }
        f[n - 1] = std::min(f[n - 1], f[0] + n);
    }
    
    // 收集所有极小同色区间的切分点
    std::vector<int> ends;
    
    for (int i = 0; i < n; i++) {
        int r = f[i];
        int nxt = i == n - 1 ? f[0] + n : f[i + 1];
        // r != nxt 说明 [i, r) 是一个不包含其他更小同色区间的“极小同色区间”
        // r < i + n 说明该区间长度严格小于 n（排除等价类只有 1 个点的情况）
        if (r != nxt && r < i + n) {
            ends.push_back(i + 1); // 在该极小区间的最左端 i + 1 处切一刀
        }
    }
    
    // 如果切分点个数为奇数（由性质知此时一定 >= 3），复制最后一个切分点凑成偶数
    if (ends.size() % 2 == 1) {
        assert(ends.size() > 1);
        ends.push_back(ends.back());
    }
    
    // 输出最少需要的新探测器数量，并将切分点前一半与后一半交叉配对
    std::cout << ends.size() / 2 << "\n";
    for (int i = 0; i < ends.size() / 2; i++) {
        int l = ends[i];
        int r = ends[i + ends.size() / 2];
        // 0-indexed 的半开区间 [l, r) 对应 1-indexed 的闭区间 [l + 1, r]
        std::cout << l + 1 << " " << r << "\n";
    }
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int T;
    std::cin >> T;
    
    while (T--) {
        solve();
    }
    
    return 0;
}

六、复杂度分析

时间复杂度：
- 读入与差分前缀异或和： $O(n + m)$ 。
- 对长度为 $n$ 的数组 p 进行排序： $O(n \log n)$ 。
- 环形后缀最小值递推及构造答案： $O(n)$ 。
- 总时间复杂度为 $\mathcal{O}(m + n \log n)$ ，在 $\sum n, \sum m \le 2 \cdot 10^5$ 下运行时间不到 0.1 秒，极其高效。
空间复杂度：仅使用了若干长度为 $n$ 的一维 std::vector，空间复杂度为 $\mathcal{O}(n)$ 。