P7562题解（贪心 + 类珂朵莉树 + 倍增 + 简单dp）
GaoKui
·
2023-07-06 18:19:33
·
题解
思维量比较大的题目，不过全部理解以后并不是很绕。这题需要理解 set 内部判断元素相等的机制才能做得出来，在做这题这之前对 set 内部的机制一直不太清楚。set 的运用比较类似于珂朵莉树，用 set 中的元素表示区间，从而进行维护。一开始只叙述大致思路，set 运用的具体细节与原理，在之后再写。
首先，可以很明显地发现这一题具有贪心性质。由于要保证答案的字典序最小，编号越小的活动被选择的优先级也就越高。用 i 从 1 至 n 遍历所有活动的编号，如果选择活动 i 后，在剩下的时间段内依然可以可以选出足够数量的活动，那么活动 i 就是必须要选择的，只有这样才能得到字典序最小的答案。
但是，想要实现以上的想法要解决两个问题：
怎么知道选择活动 i ，是否会和之前已经选择的活动发生冲突？（按题目要求，就是两条线段发生了相交，端点相交不算）
怎么知道选择活动 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 列时可以分两步走：
对所有为活动左端点的坐标特殊考虑，赋上初值
对于剩余的所有坐标，通过递推得来
首先来一个循环，用 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 内部的元素比较使用的是“严格弱序”这一种关系。这种关系的推导用了一些离散数学的知识，这里仅仅只做简单的解释。
比如，< 就是一种严格弱序，而 <= 不是一种严格弱序。使用严格弱序这一关系的好处，就是仅仅只用重载 < 一个运算符，即可完成元素的比较，不需要重载 <=、==、> 等等。
所有的比较情况如下：
$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``` 就会认为它们相等，从而自动去重。而一旦两个区间不相交，它们也一定就不相等。
代码如下：
```cpp
#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;
}
```