ABC364 DEF 题解
D - K-th Nearest
赛时想了一个（也许确实是对的）做法，但是代码太难写，一直没写出来……看了官方题解才发现正解其实也很简单……
本题最关键的一点是要转换思路：与其考虑“离某个点第 \(k\) 近的点在哪”，不如考虑“离某个点距离不超过 \(x\) 的点有多少个”。想到这一步转换，这道题就完成 \(80\%\) 了，因为之后的想法都非常顺理成章。
设 \(f_i(x)\) 表示在 \(A_1, A_2, \cdots, A_n\) 中，离 \(B_i\) 距离不超过 \(x\) 的点的数量。不难看出，只要找到最小的满足 \(f_i(x) \ge k_i\) 的 \(x\)，那么 \(x\) 就是答案。而 \(f_i(x)\) 显然是单调递增的，所以可以二分。
最后，如何计算 \(f_i(x)\) 呢？可以将 \(A_1, A_2, \cdots, A_n\) 从小到大排序，然后我们要做的就是计算落在 \([B_i - x, B_i + x]\) 中的点数。因为 \(A\) 已经有序了，可以简单地使用 lower_bound 和 upper_bound 来查找。
E - Maximum Glutton
看到这题，首先想到二维费用背包：设 \(f(i, x, y)\) 表示在前 \(i\) 道菜肴中，甜度不超过 \(x\)，咸度不超过 \(y\) 的情况下，最多能吃多少道菜肴。需要注意，因为甜度或咸度超过限度时才会停止，所以在吃掉 \(f(N, X, Y)\) 道菜肴之后，他还可以再吃一道（如果还有菜肴的话），因此答案为 \(\min(N, f(N, X, Y) + 1)\)。
但是，二维费用背包的时间复杂度是 \(O(NXY)\)，在本题中无法接受。注意到 \(N\) 很小，这时应该考虑改变状态设计，并尽可能在下标中用和 \(N\) 有关的量替换掉 \(X\)、\(Y\) 有关的量，这样就可能减小时间复杂度。
重新设计状态：设 \(f(i, j, k)\) 表示在前 \(i\) 道菜肴中选择 \(j\) 道吃掉，使得总甜度值为 \(k\) 时，这些菜肴的最小总盐度值。这样，状态的前两个维度都和 \(N\) 有关，又因为转移的时间复杂度是 \(O(1)\)（见下），所以总的时间复杂度就降到了 \(O(N^{2}X)\)。想到这样设计状态，接下来也就十分简单了。
答案统计：找到最大的满足 \(f(N, j, k) \le Y\) 的 \(j\)，则答案为 \(\min(N, j+1)\)。（\(0 \le k \le X\)）
转移方程：\(f(i, j, k) = \min(f(i-1, j, k), f(i-1, j-1, k-a_i)+b_i)\)，括号中两项分别考虑选择和不选择第 \(i\) 道菜肴。
初始化：\(f(i, j, k) = \begin{cases} 0, j=k=0 \\ +\infty, \text{Otherwise} \end{cases}\)
优化：由于 \(f(i,*,*)\) 只和 \(f(i-1,*,*)\) 有关，所以可以把第一维滚掉，空间复杂度降到 \(O(NX)\)。注意循环要改成倒序。
F - Range Connect MST
看到要求最小生成树，首先想到 Kruskal。先回忆一下 Kruskal 的流程：
- 将所有边按边权从小到大排序。
- 依次遍历所有边。对于每条边，如果它连接的两点不在同一连通块中，则把这条边加入 MST。
对于本题来说，难点在于第二步：边数最多可以达到 \(NQ\)，不可能真的遍历每条边。然而，我们真的必须遍历每条边吗？
首先，编号大于 \(N\) 的节点是不重要的，下面我们只关心编号小于 \(N\) 的节点。注意到题目中加边的形式：每次加边都会将 \([L_i, R_i]\) 中的点练成一个连通块。也就是说，如果任意的两点 \(A\)，\(B\) 联通，那么所有满足 \(A \le x \le B\) 的点 \(x\) 都和 \(A\)，\(B\) 在同一连通块中。
以样例 1 为例，用不同颜色代表不同连通块：
初始时，所有节点互不连通。
\[{\Huge{\color{red}\Box}{\color{green}{\Box}}{\color{blue}\Box}{\color{brown}{\Box}}} \]第一次操作，把 \(1\)，\(2\) 号节点连通：
\[{\Huge[{\color{green}{\Box\Box}}]{\color{blue}\Box}{\color{brown}{\Box}}} \]第二次操作，把 \(1\)，\(2\)，\(3\) 号节点所在的连通块连通：
\[{\Huge[{\color{blue}{\Box\Box\Box}}]{\color{brown}{\Box}}} \]第三次操作，把 \(2\)，\(3\)，\(4\) 号节点所在的连通块连通：
\[{\Huge{\color{brown}\Box}[{\color{brown}\Box\Box\Box}]} \]于是可以想到，把边权排序后，对于每次加边操作，从 \(L_i\) 开始，不断跳到当前点所在连通块最右边的（即编号最大）节点（不妨称这个节点的编号为 \(x\)），然后在 \(x\) 和 \(x+1\) 之间连边，直到跳出加边的区间。每次加边的时候，统计一下答案即可。（可以根据上面的图示理解。）以及，别忘了每次操作时，我们还要从编号大于 \(N\) 的节点向编号小于 \(N\) 的节点连一条边（否则不连通），统计答案时记得加上。
连通性显然可以用并查集维护。为了方便快速找到当前连通块最右边的节点，可以直接用最右边的节点作为这个连通块的代表元，这需要在 merge 的时候注意一下参数的顺序（详见代码）。
PS：ABC352E 也是一道相似的用 Kruskal 求最小生成树的题，可以去尝试一下。
标签：Box,连通,le,color,题解,菜肴,节点,DEF,ABC364 From： https://www.cnblogs.com/dengstar/p/18329016