分治题解：从递归层数到区间选点（附贪心板子）

前言

这题名字就叫“分治”，比赛时我已经把问题转化成了区间选点，但当时不知道这个常见问题该怎么贪心，卡在了这一步。

回头看代码，其实只有两步：先算最少要选几个点，才能让每个询问区间里都有一个点；再把这些点安排进一棵尽量矮的二叉树，得到最少层数。

代码不长，但这两个问题为什么能联系起来，以及区间选点为什么要按右端点贪心，还是值得单独捋一遍。最后再整理一个同样写法的板子，下次遇到就知道怎么做了。

题目大意

有一个长度为 $n$ 的数组，以及 $q$ 个询问区间 $[l_i,r_i]$。

最开始，所有询问都在 $[1,n]$ 这个大区间内，记作第 $1$ 层。在当前区间 $[L,R]$ 中，可以任选一个位置 $x$：

所有包含 $x$ 的询问，都在当前层处理掉。
剩下的询问要么完全在 $x$ 左边，要么完全在右边，分别递归到 $[L,x-1]$ 和 $[x+1,R]$，层数加一。
没有剩余询问的子区间就不用继续递归。

求一种选择方案，使所有询问被处理时的最大层数尽量小。

数据范围：$1\le T\le 10^4$，$1\le n,q\le 10^6$，$1\le l_i\le r_i\le n$；所有测试数据的 $n$ 之和、$q$ 之和均不超过 $10^6$。时间限制为 $2$ 秒，内存限制为 $1024$ MB。

输入格式

第一行输入测试组数 $T$。每组先输入 $n,q$，再输入 $q$ 行，每行两个整数 $l_i,r_i$。

输出格式

每组输出一个整数，表示最小的最大处理层数。

样例输入

样例输出

1
2
3

3
1
2

第一步：把分治层数转化为区间选点

1. 一次选择，实际上是在区间里放一个点

选出位置 $x$ 后，所有包含 $x$ 的询问都会被处理掉。这就等价于：在数轴上选一个点，让包含它的区间都被覆盖。

这里的“覆盖”只要求每个区间里至少有一个选点，并不是要把区间里的每个位置都选出来。

所以可以先考虑这个问题：

给定若干个闭区间，至少选择多少个点，才能让每个区间都包含一个选出的点？

这个模型通常叫区间选点，也可以说“最少点覆盖区间”。英文资料中称为 Interval Stabbing Problem，COMP 382 的贪心讲义使用的就是这个定义。

注意，它和博客里以前写过的“区间合并”不是同一个问题：合并区间是在求并集，而这里关心的是几个区间能不能共用一个点。例如 $[1,2]$、$[2,3]$、$[3,4]$ 可以连成一段，但不存在一个点同时落在三个区间里。

2. 最少选点数，怎么变成最少层数？

记覆盖所有询问区间所需的最少点数为 $k$。先给出结论，再解释原因：

$$
\boxed{\text{ans}=\left\lceil\log_2(k+1)\right\rceil
=\left\lfloor\log_2 k\right\rfloor+1}
$$

本题 $q\ge 1$，所以 $k\ge 1$。

先看至少需要多少层。

分治的每次选择都对应二叉树里的一个节点，节点记录选出的位置 $x$，左右子树对应两边的递归。如果最大层数是 $h$，整棵二叉树最多有：

$$
1+2+4+\cdots+2^{h-1}=2^h-1
$$

个节点，也就是最多选出 $2^h-1$ 个点。

既然所有询问都已经被处理，那么这些选点一定覆盖了所有询问区间。因此节点数至少为 $k$，必须满足：

$$
k\le 2^h-1
$$

也就是说，$h$ 至少要达到 $\lceil\log_2(k+1)\rceil$。

再看这个层数能不能做到。

假设已经找到了 $k$ 个覆盖所有区间的点，把它们从小到大排好：

$$
p_1<p_2<\cdots<p_k
$$

每次选择这组点中间的那个点作为当前分割位置，剩下的点再分别在左右两边取中间点，构成一棵平衡二叉树。

这个安排为什么不会漏掉询问？如果某个询问不包含当前选点，它就只能完全位于一侧；而它原本至少包含一个覆盖点，这个覆盖点也必定还留在同一侧。因此递归下去，它最终一定会被处理。

每次将选点数量分成尽量均衡的两半，这棵树的高度就是 $\lfloor\log_2 k\rfloor+1$；没有剩余询问的分支还可以直接停止。它恰好达到前面的下界，所以结论成立。

取中间的是排好序的选点，不一定是数组下标区间的中点。证明中需要安排这棵树，代码里只求层数，不用真的建树或递归。

3. 用样例对一下

第一组中，$[1,1]$、$[2,2]$、$[4,4]$、$[5,5]$ 强制要求分别选出 $1,2,4,5$，所以 $k=4$。这四个点也已经覆盖了 $[1,5]$，不需要再加点。

两层二叉树最多容纳 $3$ 个节点，放不下 $4$ 个点，因此答案是 $3$。

第二组的两个区间 $[1,3]$、$[3,5]$ 可以共用端点 $3$，$k=1$，答案为 $1$。

第三组有三个不同位置的单点区间，$k=3$。选 $2$ 为根，$1$ 和 $3$ 放在第二层，答案为 $2$。

第二步：区间选点怎么贪心？

现在问题只剩下：怎么求最少选点数 $k$？

方法很短：

将所有区间按右端点从小到大排序。
从前往后扫描，维护最近选出的点 last_point。
当前区间已经包含这个点，就跳过。
否则，在当前区间的右端点新选一个点。

1. 为什么选右端点？

假设当前尚未覆盖的区间里，最早结束的是 $[l,r]$。无论怎么选，都必须在这个区间里放一个点，否则它永远覆盖不到。

既然必须放，那就尽量往右放，直接选 $r$。

这不只是“看起来比较划算”，可以用替换的方法证明：假设某个最优方案在 $[l,r]$ 里选了点 $p$。对于任何原本被 $p$ 覆盖的剩余区间 $[a,b]$：

因为它包含 $p$，所以 $a\le p$。
因为 $[l,r]$ 是最早结束的剩余区间，所以 $r\le b$。
又因为 $p\in[l,r]$，所以 $p\le r$。

连起来就是：

$$
a\le p\le r\le b
$$

因此，把点 $p$ 右移到 $r$，这些区间依然全部被覆盖，选点数也没增加。也就是说，至少存在一个最优方案，第一步就选择当前最早结束区间的右端点。

删掉被它覆盖的区间，再对剩下的区间重复这个过程，贪心就成立了。

2. 为什么代码只判断左端点？

完整的覆盖条件应该是：

$$
l\le\text{last_point}\le r
$$

但我们已经按右端点排过序，last_point 又是前面某个区间的右端点，所以它一定不大于当前的 $r$。右边的条件自动满足，只需要判断：

1	if (l <= last_point) continue;

就可以了。

如果 $l>\text{last_point}$，当前区间已经位于最近选点右边，更早的选点也不可能覆盖它，此时才需要增加一个点。

3. 手推一个例子

给出四个闭区间：$[1,3]$、$[2,5]$、$[4,6]$、$[6,8]$。它们已经按右端点排序。

当前区间	最近选点	处理方式
$[1,3]$	尚未选点	选右端点 $3$
$[2,5]$	$3$	$2\le3\le5$，跳过
$[4,6]$	$3$	$4>3$，新选右端点 $6$
$[6,8]$	$6$	包含端点 $6$，跳过

最后选出的点是 ${3,6}$，最少点数为 $2$。

特别注意：这里是闭区间，端点相等也算覆盖，所以新选点的条件是 l > last_point，不能写成 l >= last_point。

顺带一提，贪心每次被迫新增选点时，对应的那些区间两两不相交。它们各自至少需要一个点，而我们的算法恰好只用了这么多个点。这也说明：

$$
\text{最少选点数}=\text{两两不相交的闭区间的最大数量}
$$

这是同一个贪心的另一个看法，不需要另外再写一套算法。对于这里的闭区间，“不相交”也不能包含共享端点的情况。

本题代码

沿用原来的写法，用 pair 的 first 存右端点、second 存左端点，这样 sort(arr, arr + q) 就是在按右端点排序；右端点相同时按左端点排序，不影响结果。

代码只把 res、pos 分别改成 point_cnt、last_point，用局部的 l,r 写清含义，并加上快速输入输出、去掉调试语句。核心贪心和最后除以二的处理都保留。

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
typedef pair<LL, LL> PII;

const int N = 1e6 + 10;
PII arr[N]; // first 存右端点，second 存左端点

int T, n, q;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> T;
    while (T--) {
        cin >> n >> q;
        for (int i = 0; i < q; i++) {
            cin >> arr[i].second >> arr[i].first;
        }

        sort(arr, arr + q); // 按右端点从小到大排序

        int point_cnt = 0;
        LL last_point = -1; // 本题端点 >= 1，-1 表示尚未选点

        for (int i = 0; i < q; i++) {
            LL l = arr[i].second, r = arr[i].first;
            if (l <= last_point) continue;

            point_cnt++;
            last_point = r;
        }

        // point_cnt 的二进制位数，就是最少层数
        int ans = 0, cnt = point_cnt;
        while (cnt) {
            ans++;
            cnt /= 2;
        }

        cout << ans << '\n';
    }

    return 0;
}

最后这个 while 算的是 $k$ 的二进制位数，也就是 $\lfloor\log_2 k\rfloor+1$。例如 $k=4$，依次变成 $4\to2\to1\to0$，循环三次，答案为 $3$。不用调用浮点数 log2，边界也好理解。

代码读入了 $n$，但后续没有用它分配数组或递归，这是正常的：$n$ 给出了合法位置范围，计算答案只需要询问区间。

复杂度

排序需要 $O(q\log q)$，扫描需要 $O(q)$，求二进制位数需要 $O(\log q)$，单组时间复杂度为 **$O(q\log q)$**。多组总时间为 $O(\sum q_i\log q_i)$。

本题代码使用大小为 N 的静态数组，存储空间为 $O(N)$，与当组实际的 $q$ 无关；其中只用到了前 $q$ 个位置。两个 LL 组成的数组元素，在通常每个 LL 为 8 字节的环境下，数组约占 16 MB。不能把 PII arr[N] 误算成只占一个整数的空间。

通用板子：闭区间最少选点

这个板子单独解决区间选点，不包含本题的层数换算。仍然用 PII 存 **{r, l}**，和上面的代码保持一致。

函数会原地排序 segs，返回选出的最少的一组点。只需要数量就取返回值的 .size()；需要具体选点位置，返回的数组里也已经有了。

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
typedef pair<LL, LL> PII;

// segs 中每个元素为 {r, l}，表示闭区间 [l, r]，要求 l <= r
vector<LL> select_points(vector<PII> &segs) {
    sort(segs.begin(), segs.end());

    vector<LL> points;
    for (auto seg : segs) {
        LL r = seg.first, l = seg.second;

        if (!points.empty() && l <= points.back()) continue;
        points.push_back(r);
    }

    return points;
}