题目：[[2024.11.10 题目]]
## 机械师 II
有 $m$ 个机器，需要处理 $n$ 条时间，第 $i$ 个事件会占用 $[l_i,r_i)$ 的时间，每个机器可以同时处理一个时事件，求能够完成的事件数量的最大值。
---
采用反悔贪心策略。以下令 $a_i$ 为 $(l_i,r_i)$ 的二元组。
不难发现，当 $m\ge n$ 的时候，我们的机器数量足够多的时候，我们的每一个机器就只用干不超过一个任务就行了。但这是理想情况。大多数情况下 $m<<n$，这代表着每一台机器可能会跑很多次任务让答案变大。
不妨对 $a$ 以 $l$ 为关键字，从左到右扫一遍，单独开一个任务队列 $Q$。首先，若 $Q$ 里面有任务，那么我们就需要将已经运行完了的任务退出 $Q$，由于答案存在单调性，我们需要对 $Q$ 中的元素按照 $r$ 排序，$Q$ 又是动态的，因此它需要是优先队列。
然后我们判断是否满足 $|Q|\le m$ 的时候，如果满足就直接将 $a_i$ 放入 $Q$，此时答案加一；否则我们可能会挑出 $Q$ 中的一个元素将其替换成 $a_i$。怎么判断我们该不该替换，应该替换哪一个元素呢？
不难发现，加入了满足条件的任务之后 $l$ 就没有用了，因为对于下一个任务的影响只取决于 $r$。那 $r$ 自然是越大越好，毕竟这样子下一个加入的任务的限制就会松一点，因此我们找到 $Q$ 中 $r$ 最大的任务，把它和 $a_i$ 的 $r$ 进行比较，如果新的任务 $r$ 更小一些那就将原本的任务替换，这便是「反悔」的过程。
需要注意的是 $Q$ 既需要查询最小值也要查询最大值，且元素可能会重复，因此不能仅使用优先队列，可以使用 STL 当中的 multiset。
```cpp
#include <fstream>
#include <algorithm>
#include <set>
using namespace std;
using LL = long long;
const LL kMaxN = 2e5 + 5;
ifstream cin("tracy.in");
ofstream cout("tracy.out");
struct Edge {
LL l, r;
friend bool operator<(const Edge &a, const Edge &b) {
return a.r < b.r;
}
} a[kMaxN];
LL n, m, ans;
multiset<Edge> s;
int main() {
cin.tie(0)->sync_with_stdio(0);
cin >> n >> m;
for (LL i = 1; i <= n; i++) {
cin >> a[i].l >> a[i].r;
}
sort(a + 1, a + n + 1, [](auto a, auto b) {
return a.l < b.l;
});
for (LL i = 1; i <= n; i++) {
for (; s.size() && a[i].l >= s.begin()->r; s.erase(s.begin())) { }
if (s.size() < m) {
s.insert(a[i]);
ans++;
} else if (s.size() && a[i].r < s.rbegin()->r) {
s.erase(prev(s.end()));
s.insert(a[i]);
}
}
cout << ans << '\n';
return 0;
}
```
## 守墓人
有 $n$ 个结点的树，根节点为 $1$。对于每一对 $(x,y)$，你需要求出有多少种不同的 DFS 序，满足序列第 $y$ 个结点是 $x$，答案对 $10^9+7$ 取模。
---
采用特殊性质。对于树呈一条链的情况，从 $1$ 开始的 DFS 序只有一种，因此好渴鹅直接通过 for 循环模拟 DFS 的路径，存储答案并输出。最后获得 $0$ 分，这一段话都是废话。
## 慈善家
给定长度为 $n$ 的序列 $a$，对于 $a$ 的任何一种重排方案所得到的 $b$，可以进行若干次操作。每次操作选定 $i$ $(1<i<n)$，如果存在 $j,k$ 使得 $a_j>a_i$ 且 $a_i<a_k$，则让 $a_i$ 加 $1$。对于每个 $b$，求出可以进行的最大操作次数，并存入有序不可重集合 $S$ 内，输出 $S$ 内的元素。
---
采用暴力。首先我们需要想到是当 $b$ 是给出的我们应该怎么做，不难整理得到 $b_i$ 可以变成它两边的最大值的最小值，因此最多能够增加的次数为 $\sum\limits_{i=2}^{n-1}\max(0,\min(\max\limits_{j=1}^{i-1}a_j,\max\limits_{j=i+1}^n a_j)-a_i)$。现在我们只需要枚举 $b$ 的所有可能即可，使用 STL 当中的 next_permutation 函数生成排列或手写 dfs 即可。时间复杂度 $\mathcal O(n!\times n^2)$ 或 $\mathcal O(n!\times n^3)$。
## 先知
给定长度为 $n$ 的序列 $a$，第 $i$ 个元素为 $a_i$。给出 $m$ 个询问，每次询问给出两个区间 $[l_1,r_1]$ 和 $[l_2,r_2]$。你需要选择两个下标 $x,y$ $(x\in [l_1,r_1],y\in [l_2,r_2])$ 满足 $\left\lfloor\cfrac{a_x}{2}\right\rfloor\le a_y<a_x$，存在 $x$ 和 $y$ 即求出 $a_x+a_y$ 的最大值，否则输出 $0$。
---
采用暴力。首先考虑最最直白纯粹没有任何优化的暴力，便是直接枚举 $x$ 和 $y$ 然后判断条件，最后将最大值记录下来。时间复杂度 $\mathcal O(n^2m)$。
考虑优化，很明显我们不一定需要枚举 $y$。我们可以将所有 $y$ 可能的取值存在 [[vector]] 里面，对这个 vector 排序，然后枚举 $x$。当我们需要找到 $y$ 配对时，我们就通过二分查找找出小于 $a_x$ 的最大元素，再判断合不合法、存入答案即可。时间复杂度 $\mathcal O(nm\log_2 n)$，获得 $20$ 分。