机械师 II
有 个机器，需要处理 条时间，第 个事件会占用 的时间，每个机器可以同时处理一个时事件，求能够完成的事件数量的最大值。
采用反悔贪心策略。以下令 为 的二元组。
不难发现，当 的时候，我们的机器数量足够多的时候，我们的每一个机器就只用干不超过一个任务就行了。但这是理想情况。大多数情况下 ，这代表着每一台机器可能会跑很多次任务让答案变大。
不妨对 以 为关键字，从左到右扫一遍，单独开一个任务队列 。首先，若 里面有任务，那么我们就需要将已经运行完了的任务退出 ，由于答案存在单调性，我们需要对 中的元素按照 排序， 又是动态的，因此它需要是优先队列。
然后我们判断是否满足 的时候，如果满足就直接将 放入 ，此时答案加一；否则我们可能会挑出 中的一个元素将其替换成 。怎么判断我们该不该替换，应该替换哪一个元素呢？
不难发现，加入了满足条件的任务之后 就没有用了，因为对于下一个任务的影响只取决于 。那 自然是越大越好，毕竟这样子下一个加入的任务的限制就会松一点，因此我们找到 中 最大的任务，把它和 的 进行比较，如果新的任务 更小一些那就将原本的任务替换，这便是「反悔」的过程。
需要注意的是 既需要查询最小值也要查询最大值，且元素可能会重复，因此不能仅使用优先队列，可以使用 STL 当中的 multiset。
#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;
}守墓人
有 个结点的树，根节点为 。对于每一对 ，你需要求出有多少种不同的 DFS 序，满足序列第 个结点是 ，答案对 取模。
采用特殊性质。对于树呈一条链的情况，从 开始的 DFS 序只有一种，因此好渴鹅直接通过 for 循环模拟 DFS 的路径，存储答案并输出。最后获得 分，这一段话都是废话。
慈善家
给定长度为 的序列 ，对于 的任何一种重排方案所得到的 ，可以进行若干次操作。每次操作选定 ，如果存在 使得 且 ，则让 加 。对于每个 ，求出可以进行的最大操作次数，并存入有序不可重集合 内，输出 内的元素。
采用暴力。首先我们需要想到是当 是给出的我们应该怎么做，不难整理得到 可以变成它两边的最大值的最小值，因此最多能够增加的次数为 。现在我们只需要枚举 的所有可能即可，使用 STL 当中的 next_permutation 函数生成排列或手写 dfs 即可。时间复杂度 或 。
先知
给定长度为 的序列 ，第 个元素为 。给出 个询问，每次询问给出两个区间 和 。你需要选择两个下标 满足 ，存在 和 即求出 的最大值，否则输出 。
采用暴力。首先考虑最最直白纯粹没有任何优化的暴力，便是直接枚举 和 然后判断条件，最后将最大值记录下来。时间复杂度 。
考虑优化，很明显我们不一定需要枚举 。我们可以将所有 可能的取值存在 vector 里面，对这个 vector 排序，然后枚举 。当我们需要找到 配对时，我们就通过二分查找找出小于 的最大元素，再判断合不合法、存入答案即可。时间复杂度 ，获得 分。