IOI 2015 Teams 分组

题意

班里有 \(N\) 个学生,他们的编号为从 \(0\) 到 \(N-1\)。每天，老师都有一些项目需要学生去完成。每个项目都需要由一组学生在一天内完成。项目的难度可能不同。对于每个项目，老师知道应该选择由多少学生组成的小组去完成。

不同的学生对小组的规模有不同的喜好。更准确地说, 对学生 \(i\) 而言, 他只愿意在小组规模介于 \(A[i]\) 和 \(B[i]\) 之间（含 \(A[i]\) 和 \(B[i]\)）的小组工作。每一天，一个学生最多只能被分配到一个小组工作。有些学生可能未被分配到任何小组中。每个小组只负责一个项目。

老师已选择好接下来 \(Q\) 天中每一天的项目。对于每一天, 现需要判断是否有一种分配学生的方案，使得每个项目都有一个小组负责。

题解

很好的一道题啊。
参考的是这篇题解，写得很好，自己再来复述一遍。

贪心

首先我们考虑怎么处理单次询问，有一个显然的贪心做法。

将 \(k\) 数组从小到大排序，按顺序对于每一个 \(k_i\) 取满足 \(A_i \leq k_i,k_i \leq B_i\) 中 \(B_i\) 的最小的 \(k_i\) 个。

正确性显然，这种贪心题还挺多的。

优化

接下来我们显然就是要对上面的贪心进行优化。

考虑将元素看做二维平面上的点，学生变为 \((A_i,B_i)\) ，任务变为 \((k_i,k_i)\)。
我们发现对于一个点 \((k_i,k_i)\) 来说，他可以选择的学生满足 \(A_i \leq k_i,k_i \leq B_i\) 即坐标在其左上角，可以看做是一个矩形的点。
将贪心的操作映射到二维平面上就相当于在矩形之内选择未被选择的 \(B_i\) 最小的 \(k_i\) 个点。
而同时由于我们提前将 \(k_i\) 进行了排序，所有的 \(k_i\) 都类似一条斜线地排列着，就相当于每到下一个矩形下边界就向上提，右边界就向右扩。

现在我们理清楚了贪心对应到到二维平面上的形态了，接下来考虑如何解决问题。

我们考虑对于每一个矩形所选择的点，显然都和前面的选择有关，所以我们想一想要记录什么才能知道如何推出后面的状态。
注意到我们是寻找最小的 \(B_i\) ，这显然和高度有关，而一个矩形的前面的矩形没有选择的范围显然是一段一段的。
所以我们对于一个矩形记录一个 \(H_i\) ，表示第 \(i\) 个矩形未选择的点的最低高度，也就是最小的 \(B_i\) 。

这样我们就能够知道前面的选择和当前选择的关系。
若 \(H_{i-1} < B_i\) 则第 \(i\) 矩形可以选的点都不会被第 \(i-1\) 个矩形选到。
若 \(H_{i-1} > B_i\) 则第 \(i\) 矩形可以选的点可能 \(i-1\) 个矩形选到。
容易发现这和前面的矩形都有关，并且每个矩形的有效区域不一样，所以我们还需要记录一个 \(rem_i\) 表示第前 \(i\) 矩形还剩多少点可以选择。
这样我们就可以用 \(rem_{i-1}\) 和右边界所扩展出的点数来推出当前矩形的可用点数。
但是下边界还要向上扩导致一些点会消失，那我们可以维护一个 \(H_i\) 递减的单调栈来解决。
然后我们会发现这道题就解决了，通过维护 \(H_i\) 和 \(rem_i\) 可以推出每一个矩形的可用点，平面内数点和维护 \(H_i\) 显然都可以使用主席树来维护。code