自动搬运

查看原文

来自洛谷，原作者为

	GaoKui **

搬运于2025-08-24 22:31:03，当前版本为作者最后更新于2023-07-06 18:19:33，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

思维量比较大的题目，不过全部理解以后并不是很绕。这题需要理解 set 内部判断元素相等的机制才能做得出来，在做这题这之前对 set 内部的机制一直不太清楚。set 的运用比较类似于珂朵莉树，用 set 中的元素表示区间，从而进行维护。一开始只叙述大致思路，set 运用的具体细节与原理，在之后再写。

首先，可以很明显地发现这一题具有贪心性质。由于要保证答案的字典序最小，编号越小的活动被选择的优先级也就越高。用 $i$ 从 $1$ 至 $n$ 遍历所有活动的编号，如果选择活动 $i$ 后，在剩下的时间段内依然可以可以选出足够数量的活动，那么活动 $i$ 就是必须要选择的，只有这样才能得到字典序最小的答案。

但是，想要实现以上的想法要解决两个问题：

1. 怎么知道选择活动 $i$，是否会和之前已经选择的活动发生冲突？（按题目要求，就是两条线段发生了相交，端点相交不算）
2. 怎么知道选择活动 $i$ 前后，剩余的空余时间里还能选择多少个活动？

---

对于问题 $1$：

本题可以通过用 set 来维护 空闲时间 来解决问题 $1$。这和珂朵莉树是类似的，set 中每一个的元素表示的是一段区间，这段区间是空闲的，能够在其中参加若干个活动。

一个活动可以选择的条件是：它的起始时间和结束时间必须位于同一段空闲时间当中（对应题目中说的，不能在一个活动进行的中间加入或离开这个活动）。那么，判断活动 $i$ 是否可选，就变为了判断是否能在 set 中找到一个元素，使得这个元素代表的区间可以完全包含活动 $i$。如果可以完全包含，就必须要选择活动 $i$，以此保证答案字典序最小。选择以后，活动 $i$ 将找到的这个完全包含的元素分割为两个新的元素，即：

假设，找到的元素为 $[l,r]$，活动 $i$ 为 $[x,y]$。那么，活动 $i$ 会将找到的元素分割为 $[l,x]$，$[y,r]$ 两个部分。因此，我们只需要在 set 中删除 $[l,r]$ 所代表的元素，重新插入 $[l,x]$，$[y,r]$ 两个元素即可。

但是，怎么在 set 中找到一个可以完全包含活动 $i$ 的元素呢？简单地说，就是对于表示区间的结构体，重载小于号时使用一些特殊的方法， 即：

bool operator<(const Seg &rhs) const
{
	return r < rhs.l;
}

这样重载以后，就能直接调用 set::find() 函数进行查找。

比如，活动 $i$ 为 $[x,y]$，就直接调用 set::find({x, y})。此时，该函数会返回一个与 $[x,y]$ 这个区间相交的区间，而如果没有元素与 $[x,y]$ 相交，则会返回 set::end()。此时特判一下，如果这个与 $[x,y]$ 相交的元素能够完全包含活动 $i$，则找到了符合规定的元素，在答案里，就可以选择活动 $i$，然后在 set 里进行上面说过的分割操作，否则，不能找到完全包含活动 $i$ 的元素，活动 $i$ 不能选择。

之所以能够按以上方法寻找相交区间，是因为按照以上方法重载小于号后，set 会将相交的两段区间认为是相等的元素。这样做还有另一个好处，可以保证算法正确性。即，任何两个相交的元素都会被 set 认为相等，也就是会被自动去重。

这样一来，虽然可能有多个元素与活动 $i$ 相交，但是，此时一定不会存在任意一个元素能完全包含活动 $i$。因此，这种情况下，找到任意一个与活动 $i$ 相交的元素，特判的结果一定都是不合法，不会影响正确性。反之，如果存在一个元素能完全包含活动 $i$，则它一定是唯一一个与活动 $i$ 相交的元素，一定可以通过特判。

但是为什么这样重载小于号后，set 就会认为两个相交的区间是相等的？这就涉及到了 set 的内部机制，之后再做说明。

---

对于问题 $2$：

如果有一个 $query$ 函数，可以返回在 $[l,r]$ 这段区间里可以选择多少个活动，那么就可以通过在问题 $1$ 中实现的，维护空闲时间来解决这个问题。

一开始的剩余时间为 $[start, end]$，其中 $start$ 和 $end$ 是所有活动中最早的开始时间和最晚的结束时间（不过这个时间是经过了离散化的，这个后面会讲，暂时不用管）。用一个计数器 $last$ 记录当前可选的活动数量，一开始这个变量的值为：

query(start, end);

之后，用 $i$ 循环 $1$ 至 $n$ 的所有活动编号

假设活动 $i$ 代表的区间为 $[x,y]$，在问题 $1$ 中，查找到的完全包含活动 $i$ 的元素为 $[l,r]$。那么，选择了活动 $i$ 以后，剩下的空余时间还能选择的活动数目就能这么计算：

last - query(l, r) + query(l, x) + query(y, r);

式子并不难理解，即原本的 $[l,r]$ 这段区间被拆成了 $[l,x]$，$[y,r]$，剩余可选的数目就要减去老区间，再加上两个新区间。由于活动不能在进行过程中加入或退出，即不可能出现跨越两段分隔开的区间的活动，按以上方法计算出来的结果一定是正确的。只要计算出的这个值，大于等于剩余需要选的活动个数，活动 $i$ 就是要选的。

现在关键的问题就是，如何实现这个 query 函数？

这是本题思维量最大的一个地方，设 $f[i][j]$ 表示从坐标为 $i$ 的点，往右挑选 $2^j$ 个活动后能够到达的最靠左的坐标为多少。由于坐标的取值范围最大到 $10^9$，直接开这样的 $f$ 矩阵是会爆空间的。因此，首先要对坐标进行离散化。这个状态表示确实不容易想到，这么做的理由在下面 query 函数的实现中可以体会到。

query 函数中，利用倍增进行查询。

目的是调用 query(l, r)，利用 $f$ 矩阵，返回 $[l,r]$ 这段区间里最多可以选择多少个活动。初始化 $res = 0$，$cur = l$。$res$ 是最后要返回的答案，$cur$ 是当前位置的坐标。

用 $j$ 从大到小遍历 $log_2(N)$ ~ $0$，由于 $f[cur][j]$ 就是往右选 $2^j$ 个活动能到达的最左边的坐标，一旦发现 $f[cur][j]$ 的值在 $r$ 左边，或者刚好跳到 $r$ 上，说明可以往右选 $2^j$ 个活动。此时，令 $cur = f[cur][j]$，跳到对应的坐标，$res = res + 2^j$，加上选择的活动数。最后结束循环，返回 $res$ 即可。

通过以上的过程，也能体会到为什么 $f$ 要这么定义。

之所以 $f[i][j]$ 表示的是尽量靠左的一个坐标值，就是因为在选取 $2^j$ 个活动后，还想要最大化剩余可选的活动数，就要让选择后剩余的区间也尽量地更大一些，即往右跳的距离尽量小一些。所以，$f$ 的值是向右挑选 $2^j$ 个活动后，尽量靠左的坐标值。

接下来，考虑如何求出 $f$ 矩阵。

先解决一个问题，解释一下为什么可以套用倍增的板子，即：

f[i][j] = f[f[i][j - 1]][j - 1]

首先，要选 $2^j$ 个活动，同时要保证选完后的坐标最靠左，那么每一步的选择都是一定的。首先假设 $j$ 为常数，可以发现，$i$ 这个值越靠右，$f[i][j]$ 也一定越靠右。

因为，如果 $f[i+1][j]$ 反而比 $f[i][j]$ 更靠左，那 $f[i][j]$ 显然可以更新成 $f[i+1][j]$。

所以，先不考虑倍增地往右选，而是一个个地往右选，那么往右选的每一个活动，都要保证选完后坐标更靠左，最终的所在的坐标才会最靠左。也就是说，选择的方案也具有贪心性质。

那么，想要使得 $i$ 往右选 $2^j$ 个活动后，所在坐标最靠左，选择 $2^{j-1}$ 个活动的时候也要让坐标尽量靠左。想要选择 $2^{j-1}$ 个活动的时候尽量靠左，就要让选择 $2^{j-2}$ 个活动时尽量靠左。以此类推，只要求出往右选择 $1$ 个活动时最靠左的下标，之后就可以利用倍增进行递推了。

所以现在，对于 $f$ 矩阵，最关键的就是如何求出第 $0$ 列，后面的列直接用倍增板子就全求出来了，递推式如上。

怎么求出第 $0$ 列呢？首先，对于每一个坐标，如果它是活动的左端点，那就可以选择这个活动，到达这个活动的右端点处。而如果某个坐标，它并不是活动的左端点，而是在活动的中间，由于活动不能在中途加入，它就不能选择这一个活动了。而对于不在活动线段上的坐标，同样也是没法直接得到结果的。

因此，对于不是活动左端点的坐标，唯一的方法就是从它右边的某一个点递推而来。综上，求第 $0$ 列时可以分两步走：

1. 对所有为活动左端点的坐标特殊考虑，赋上初值
2. 对于剩余的所有坐标，通过递推得来

首先来一个循环，用 $i$ 遍历所有活动 为方便描述，令 $l[i]$ 表示活动 $i$ 的左端点，$r[i]$ 表示活动 $i$ 的右端点，式子就可以表示为如下形式：

f[l[i]][0] = min(f[l[i]][0], r[i]);

然后再来一个循环，用 $i$ 从右到左遍历所有坐标（当然是离散化过的），按照下式进行递推：

f[i][0] = min(f[i][0], f[i + 1][0]);

经历了以上两个循环，$f$ 矩阵的第 $0$ 列已经被求出来了。之后用倍增即可得出 $f$ 矩阵。得出 $f$ 矩阵，即可使用 query 函数。可以使用 query 函数，也就解决了问题 $2$。解决了问题 $2$，之前也说了如何解决问题 $1$，那么这一题也就能够解决了。

---

最后的问题。

为什么按照上面的小于号重载方式，两段相交的区间会被 set 认为是相等，并且自动去重？

又是为什么，我们用 set::find() 查找一个区间，查询到的结果会是一个可能与查询区间不同，但一定与查询区间相交的区间？

set 内部的元素比较使用的是“严格弱序”这一种关系。这种关系的推导用了一些离散数学的知识，这里仅仅只做简单的解释。

比如，< 就是一种严格弱序，而 <= 不是一种严格弱序。使用严格弱序这一关系的好处，就是仅仅只用重载 < 一个运算符，即可完成元素的比较，不需要重载 <=、==、> 等等。

所有的比较情况如下：

$a$ 小于 $b$ --> a < b

$b$ 小于 $a$ --> b < a

$a$ 等于 $b$ --> !(a < b) && !(b < a)

关键点就在于最后的等于这个判断。

---

第一种相交情况：相交，但不包含。

假设有两个结构体，分别表示两段区间 $a$：$[1,4]$、$b$：$[2,5]$。

按照上面的小于号重载方式手动验算，得到的结果正好就是 !(a < b) && !(b < a) 因此，这种情况下，set 就会认为这两个元素是相等的。

---

第二种相交情况：相交且包含。

假设有两个结构体，分别表示两段区间 $a$：$[1,5]$、$b$：$[2,4]$。

按照上面的小于号重载方式手动验算，得到的结果正好也是 !(a < b) && !(b < a)

---

第三种情况：不相交 简单想象一下便知，此时，一定有某一个区间的右端点小于另一个区间的左端点。无论如何，这两个不相交的区间是不会被认为是相等的。

---

综上所述，一旦两个区间产生了相交，set 就会认为它们相等，从而自动去重。而一旦两个区间不相交，它们也一定就不相等。

代码如下：

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10;

struct Seg
{
    int l, r; // 区间的左右端点

    Seg(int x = 0, int y = 0) // 构造函数，默认形参为 0
    {
        l = x;
        r = y;
    }

    bool operator<(const Seg &rhs) const // 重载小于号，用于 set 的内部排序（不重载小于号，结构体不能放入 set）
    {
        return r < rhs.l;
        // return r <= rhs.l;

        // 如果用 <=，那么两条区间的端点重合时不会被认为是相等的元素，所以直接用 < 就行
        // （不过似乎两种方法都是对的）
    }
};

int n, k;
Seg s[N];           // 存储所有的活动
vector<int> all;    // 存储所有活动端点，之后用于离散化

int f[2 * N][19];   // f[i][j] 的含义如上，第二列是对 2*N 取以 2 为底对数的大概值

set<Seg> st;        // 用 set 维护空余时间，对于这点上面已经描述过了

// 利用倍增与简单的 dp，得到 f 矩阵
void get_f(void)
{
    memset(f, 0x3f, sizeof(f)); // 把整个矩阵初始化为最大值

    for (int i = 1; i <= n; i++) // 先通过所有活动的左右端点，赋上最初的初值
    {
        f[s[i].l][0] = min(f[s[i].l][0], s[i].r);
    }

    for (int i = all.size() - 1; ~i; i--) // 从右往左遍历离散化后的坐标，递推得出完整的第 0 列
    {
        f[i][0] = min(f[i][0], f[i + 1][0]);
    }

    // 用倍增板子，得出整个 f 矩阵
    for (int p = 1; p < 19; p++) // 外层循环枚举列
    {
        for (int i = 0; i < all.size(); i++) // 内层循环枚举行
        {
            // 如果往右选 2^(p-1) 个活动后跳到的坐标，是一个合法坐标才能进行递推
            // 否则，f[f[i][p - 1]][p - 1] 里的行号就是不合法的，调用后会数组越界
            if (f[i][p - 1] < all.size())
            f[i][p] = f[f[i][p - 1]][p - 1];
        }
    }
}

// 查询空闲区间 [l,r] 中最多能够选出几个活动
int query(int l, int r)
{
    int res = 0;
    int cur = l; // 初始位置位于左端点处

    for (int p = 18; ~p; p--)
    {
        if (f[cur][p] <= r)     // 往右选 2^p 个活动后不会超过右端点，那就选
        {
            cur = f[cur][p];    // 选了 2^p 个活动，跳到对应的位置
            res += (1 << p);    // 统计刚选上的 2^p 个活动
        }
    }

    return res; // 上述循环结束后 res 就是所求答案
}

// 用 x 与 y 构造出一个左端点为 x，右端点为 y 的元素，并将其返回
Seg make(int x, int y)
{
    Seg tmp(x, y);
    return tmp;
}

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

    // cout << log2(2 * N) << '\n'; // 17.6098

    cin >> n >> k;

    for (int i = 1; i <= n; i++)    // 输入所有的活动
    {
        cin >> s[i].l >> s[i].r;
        all.push_back(s[i].l);      // 把每一个出现的左右端点放到 all 里，之后用于离散化
        all.push_back(s[i].r);
    }

    sort(all.begin(), all.end());               // 离散化前排序
    auto ed = unique(all.begin(), all.end());   // 离散化前去重
    all.erase(ed, all.end());                   // 把调用 unique 后放到最后的重复元素，直接删除，这样一来 all 的大小就是最右边的坐标值

    for (int i = 1; i <= n; i++)
    {
        s[i].l = lower_bound(all.begin(), all.end(), s[i].l) - all.begin(); // 令每个活动的端点变为离散化后的值
        s[i].r = lower_bound(all.begin(), all.end(), s[i].r) - all.begin();
    }

    get_f(); // 得到 f 矩阵

    // st 内维护的是空闲时间段，一开始，整个坐标轴都是空闲时间，因此插入的元素就是代表整个坐标轴的区间
    // 即，左端点是最左边的坐标，右端点是最右边的坐标
    st.insert(make(0, all.size() - 1));

    vector<int> res;                        // res 里保存最终要输出的活动编号
    set<Seg>::iterator it;
    int last = query(0, all.size() - 1);    // 一开始，所有空余时间段内能够选择的活动数，就是整个坐标轴上能选的活动数

    for (int i = 1; i <= n && res.size() < k; i++)      // 从 1~n 遍历每一个活动，遍历完所有活动或已选活动数达到 k 个后退出循环
    {
        if ((it = st.find(s[i])) == st.end()) continue; // 没有能与当前活动相交的空闲区间，直接跳过就好

        // it 现在指向的元素，就是与活动 i 相交的某一个元素

        if (s[i].l >= it->l && s[i].r <= it->r) // 如果该元素完全包含了活动 i，则继续进行考虑，否则跳过就好
        {
            // 如果选完这个活动以后，剩下的空余时间里依然能选出足够的活动，那就选上这个活动
            if (last - query(it->l, it->r) + query(it->l, s[i].l) + query(s[i].r, it->r) >= k - res.size() - 1)
            {
                last = last - query(it->l, it->r) + query(it->l, s[i].l) + query(s[i].r, it->r);    // 剩余能选的活动数对应减少
                res.push_back(i);                                                                   // 把当前活动存入 res
                Seg t1(it->l, s[i].l), t2(s[i].r, it->r);   // 两个新的要插入的元素，即被活动 i 分割开来的两个区间
                st.erase(it);                               // 删除旧的元素
                st.insert(t1);                              // 插入两个新元素
                st.insert(t2);
            }
        }
    }

    if (res.size() == k) // 退出循环后，如果已经选出了 k 个活动
    {
        for (auto j : res) // 输出选择的活动
        {
            cout << j << '\n';
        }
    }
    else // 否则说明无法选出 k 个活动
    {
        cout << -1;
    }

    return 0;
}