一类 kth 相关问题

​ 实际上，这个 trick 以及其拓展在去年 noip 级别的模拟赛已经用到了多次，但是认知仅局限于“用优先队列”解决的一类题目，有时可以直接建立最短路模型。在去年一场 nfls 中甚至因为知道此 trick 而在最后一题狂砍 50 分，今天在 dmy 再遇，故整理其成体系。

T4 控制

有 \(n\) 类装备，每种类型有 \(m_i\) 种，且各有一个魔力值，定义一个方案为每一类选一个；你要求出前 \(k\) 大方案的魔力值总和。

套路题，优秀的暴力是 用优先队列维护，类似搜索，从一个状态向外转移，并加入堆里。为了避免加重，需要加入顺序的约定。

正解比较复杂，但发现本质和 \(dij\) 很像，所以可以转换成图论，建立 \(nm\) 个点，每个第 \(i\) 类的点，向每个第 \(i+1\) 类的点连边。直接可并堆优化 k 短路即可。需要虚拟源点和汇点。

0.模型与思路

给定你一个价值的计算方案，具体又可分为序列上子集和，子区间（超级钢琴），树上连通块。要求输出其第 \(k\) 大的价值，或前 \(k\) 大价值的和。\(k\) 通常在 \(10^5\) 级别，而还有一类 \(k=10^{18}\) 类似的问题通常是使用二分答案解决。

这一类问题有通用思路：

对于目前考虑到的一个状态 \(S\)，设 \(trans(S)\) 为 $S $ 的后继状态集合。首先将最优的 \(S\) 放进堆中，重复下列操作 \(k\) 次。

• 取出堆顶 \(S\)，计算 \(S\) 的答案。
• 将所有 \(trans(S)\) 放入堆里。

可以注意到，如果 \(|trans(S)|\) 是 \(O(1)\) 或者 \(O(\log)\) 的，且都劣于 \(S\)，而且需要保证 \(S\) 的状态不重不漏时算法可以在 \(O(n\log n)\) 或者 \(O(n\log ^2 n)\) 的时间复杂度内完成。问题的关键在于构造一个不重不漏的 \(trans(S)\)。

1.Multiset

给定一个可重集 \(S\)，求大小为 \(p\) 的第 \(k\) 小子集。

首先排序，最优一定是前 \(p\) 项。先不考虑 \(|trans(S)|\) 大小的限制，先满足不重不漏，因为这样我们至少能得到多项式复杂度的做法。

初始时 \(S_0\) 为排序后的前 \(p\) 个数，考虑以下构造方案：

• 每次将最右侧的未移动点向右移动若干位，但不能跨越已移动点。
• 将其标记为已移动点。

容易发现，对于任何一个大小为 \(p\) 的状态，都有且仅有一种操作方案。实际上类似于二进制上逐位确定的方法。

我们可以将转移抽象为树的形式，这样做的问题就在于，节点的儿子实在太多了。

但是只要保证解是逐渐变劣的，那么这棵树的形态是不重要的，那么我们可以用树的兄弟儿子表示法将树三度化，也就是说，每个节点只存它最优的儿子和向右第一个兄弟。

设四元组 \((val,x,y,z)\) 表示权值和为 \(val\)，最长未移动前缀为 \(x\)，当前移动项为 \(y\)，右侧首个已移动项为 \(z\)。

• \((val,x,y,z)\to (val-v_y+v_{y+1},x,y+1,z)\) 表示最右侧的可移动点向右移动一格，也就是向右第一个兄弟。需要保证 \(y+1<z\)。
• \((val,x,y,z)\to (val-v_x+v_{x+1},x-1,x+1,y)\) 表示将当前 \(x\) 向右移动一格。也就是最优的儿子。

不难发现，\(x,y\) 的意义相当于于下次操作和这次操作的位置。初始加入 \((sum,p,n+1,n+1)\)。用小根堆维护，时间复杂度 \(O(n\log n)\)。如果拓展至大小在 \([l,r]\) 区间中的子集，那么初始是对每个 \(p\in [l,r]\) 都加入即可。注意这里 \(n+1\) 实际上是 \(\inf\)。

例题：CF1250I。

2.Arrays

\(n\) 个数组，每个数组选一个数，求第 \(k\) 小和。

\(O(n^2\log)\) 的做法即是记录每个数组选到第几个位置。（注意去重：格外记录 \(i\) 表示钦定前 \(i\) 个已经选定了）。

最小的肯定是每个数组选第一个数。套路的，每个数组内部升序排序，设 \((val,x,y)\) 表示当前考虑到第 \(x\) 个数组，第 \(x+1\sim n\) 的数组全部只选第一个元素，第 \(x\) 个数组选第 \(y\) 个元素，这样同样可以保证转移只会变劣不会变优：

• \((val,x,y)\to (val,x+1,1)\) 表示考虑到下一个数组。
• \((val,x,y)\to (val-a_{x,y}+a_{x,y+1},x,y+1)\) 表示考虑当前数组的下一个位置。
• 初始为 \((\sum a_{i,1},1,1)\)。

但是这样会算重，很简单，你在 \(\{2,1,1,1,1\}\) 往下还会转移到 \(\{2,1,1,1,1\}\)。所以我们钦定每次只能向后转移到 \((x+1,2)\)。

那当前数组想取第一个位置怎么办呢？我们只需在每个 \((x,2)\) 新增第三个转移：

• \((val,x,2)\to (val-a_{x,2}+{a_{x,3},x,3})\)。
• \((val,x,2)\to (val-a_{x+1,1}+{a_{x+1,2}},x+1,2)\)。
• \((val,x,2)\to (val-(a_{x,2}-a_{x,1})+(a_{x+1,2}-a_{x+1,1}),x+1,2)\)。

但是注意：我们仍然要保证不断变劣（递增），而 \(-(a_{x,2}-a_{x,1})+(a_{x+1,2}-a_{x+1,1})\) 可能是负数，但是我们只需要数组间按照 \((a_{x,2}-a_{x,1})\) 递增排序即可。有点类似“反悔”的操作。

细节：对于长度为 \(1\) 的数组，我们必须选且不能改变，所以提前算出这些的和，不把他们插进 vector 里即可。

例题：P2541 [USACO16DEC] Robotic Cow Herd P。

与 k 短路的联系：不难发现本题可以直接图论建模，分层图求 k 短路，不过有些小题大做了。

3.Multisets(Shopping Plans)

有 \(n\) 个物品，每个物品有种类 \(a\) 和价格 \(c\)。

对于第 \(j\) 个种类，购买个数必须在 \([x_j,y_j]\) 的限制内。输出价格前 \(k\) 小的方案。

将两者结合起来。外层仍然是 Arrays 的做法，转移到当前数组的下一个位置 \((x,y)\to (x,y+1)\) 就是 Multiset 取到下一个子集。

数组间是按照 \(a_{j,x_{j}+1}-a_{j,x_{j}}\) 排序的。

说起来容易，实现起来或许非常困难。主要在于本题出人意料的特殊情况处理。

4.Tree

求树上第 \(k\) 小连通块点权和。

先考虑包含根的连通块，对有根树求出 dfs 序，建立一张新图：

• \(i\to i+1\) 表示选择 \(id_i\) 这个点。
• \(i\to i+siz_i\) 表示跳过 \(i\) 的子树。

然后问题转换为 DAG k 短路。外面再套一层点分治，即可将无根转换为有根。复杂度 \(O(n\log^2)\)。

5.Permutation

雷暴太强大：关于一类求前 k 优解的问题 - Cry_For_theMoon - 博客园 (cnblogs.com)。