偏序结构第 K 小问题算法小结

本文绝大部分参考 Naitir - 「技巧总结」第k小和贪心问题，是在此基础上的解说。

符号约定：$[n]$表示集合$\{1, 2, \ldots, n\}$。

前言

第 k 小（大）的问题定义在全序集合上，相关算法不胜枚举。常用的方法有二分转化为计数问题解决、数据结构直接维护、离线后整体二分等等。

大部分方法都建立在所求答案结构相对简单，亦或是全序结构比较特殊，容易计数的前提下。然对于一类全序结构无特殊性质，只可知前驱后继，甚至连前驱后继都难以判断，只能断言比之优劣的结构，上述算法将难以有效。这也是本文的算法解决的问题。

为了方便大家理解，我们以一个例题引入。

【例题】子集第 K 小问题

有一个长度为$n$的正整数序列$a_1, \ldots, a_n$。对于一个$[n]$的子集$T$，记$f(T) = \sum_{i \in T} a_i$表示一个子序列的价值。对于所有$2^n$个子序列的价值，求其中的第$k$小值，并输出方案。

$n, x, k\le 10^6$。

本题的特点是：全序结构规模过大（$O(2^n)$），并且结构没有特殊性质，难以计算一个方案的前驱后继。

但是对于子集$T \subseteq S$，我们可以容易地判断某些方案一定是比它大的。例如对于$e \notin T$，一定有$f(T\cup \{e\}) > f(T)$。换言之对于一些与$T$相关的方案我们可以断言它们与$T$的大小关系。

分析出这些信息后，容易想到维护一个小根堆。初始时将空集加入堆。每次取出堆顶的集合，记作$T$。并将【一部分与$T$相关的比$T$大】的集合都加入堆中。这样做$k$次操作后得到的就是第$k$小的方案。

问题转化为：【一部分与$T$相关的比$T$大】的集合究竟是哪些集合？

为了方便叙述，我们称【一部分与$T$相关的比$T$大】为被$T$拉入堆中。称$T$是它们的引子。它们是$T$的继子。

方法一

对于所有$e\notin T$，将$T\cup \{e\}$加入堆中。

这个方法显然不具备正确性，因为一个集合具有多个引子，会出现重复加入的情况。

方法二

只在子序列末尾加入，即对于$T$中的最大值$i_{\max}$（对于空集，$i_{\max} = 0$），考虑所有$i_{\max} < e \le n$，将$T\cup \{e\}$加入堆中。

这个方法具备正确性，因为每个非空集合有且仅有一个引子。

而这个方法的时间复杂度是$O(nk\log (nk))$，空间复杂度$O(nk)$。因为一个集合有$O(n)$个继子。

详细的正确性说明

每个集合有且仅有一个引子，说明每个集合一定会在某个时刻被拉入堆中。

而根据小根堆的性质，对于一个集合$T$，只有比他小的集合都被取出过堆顶后，它才会被取出。

因此第$k$次取出的堆顶一定是第$k$小的方案。

换言之，【非初始集合具有唯一引子】的方法都是正确的算法。

方法三

方法二的主要缺陷是继子过多，导致时空复杂度过大。换言之我们需要找到一个引子唯一，继子$O(1)$的偏序结构。

考虑将$a$从小到大排序。

那么对于集合$T$，我们将$T$中某一元素$i$加$1$（前提是$i + 1$不在$T$中）得到的集合$T'$一定是比$T$大的。

因此我们的方法是对于集合$T$，设其中的最大值是$i_{\max}$（对于空集，$i_{\max} = 0$）。若$i_{\max} < n$，那么我们就将$T \cup\{i_{\max} + 1\}$和$T\cup \{i_{\max} + 1\}\setminus \{i_{\max}\}$分别加入堆中。通俗地说，要么我们将子序列最后一个下标加一，要么就加一个数到子序列中。

这个方法显然具备正确性。并且复杂度足够优秀，为$O(k\log n)$。

小结

由于全序结构的不明显，因此传统的全序算法在这个问题上难以适用。

上述的算法的本质是利用结构中隐藏的偏序性质（一些与$T$相关的方案我们可以断言它们与$T$的大小关系）组合构建出全序结构，通过小根堆维护以优化复杂度。

简单来说传统的方法是从最小值开始找$k$次后继，找的是一个集合的后继。而堆维护偏序算法干的事情是，找若干个集合的后继，即踢掉最小的，将更多可能的后继加入。

【例题】 扩域版第 K 小问题

给出$n$个正整数集合，第$i$个集合记作$A_i$，其中的第$j$小的数记作$A_{i, j}$。现在要从每个集合里拿出了一个数，方案的价值是拿出的数的和，求第$k$小的代价是多少。

$n, \sum |A_i|, k \le 10^6$。

延续子集第 K 小的思路，考虑用堆维护偏序。

考虑一个选数方案$(j_1, \ldots, j_n)$其中$j_i$表示第$i$个集合选$A_{i, j_i}$。可以发现，将其中任意一个（可以增大的）$j_t$加一得到的方案都是比它大的。

那么初始时将$(1, 1, \ldots, 1)$加入堆中。同时我们将集合按照$A_{i, 2} - A_{i, 1}$从小到大排序。

为了保证引子唯一，我们找到方案中最大靠后的$>1$的元素对应的下标$t$（即最大的$t$使得$j_t > 1$，若没有则$t = 0$）：

• 若$t > 0$且$j_t < |A_t|$，将$(j_1, \ldots, j_{t - 1}, j_t + 1, j_{t + 1}, \ldots, j_n)$加入堆中。
• 若$t < n$，将$(j_1, \ldots, j_t, j_{t + 1} + 1, \ldots, j_n)$（等价于$(j_1, \ldots, j_t, 2, \ldots, j_n)$）加入堆中。排序保证了这一步的正确性。

这样可以保证引子唯一，进而保证算法正确性。时间复杂度$O(k\log n)$。

传统算法能否给劲

对于这类问题，其实传统算法思想并非毫无用武之地。

利用传统算法思想我们可以获得复杂度稍劣但更为普遍的解法。

【另解】（扩域）子集第 K 小问题

仍然是子集第 K 小问题，这次我们从二分的角度思考。

二分答案$x$后，问题转化为求权值和小于等于$x$的方案数。

仍考虑用堆维护答案。我们用堆维护前$i$个元素的方案中权值和小于等于$x$的所有方案。

考虑加入$a_{i + 1}$，那么我们枚举堆中每一个元素$s$，如果$a_{i + 1} + s\le x$就将$a_{i + 1} + s$加入堆中。

一旦堆的大小超过$k$就停止 check。

这个算法的复杂度视实现情况为$O(k\log k\log V)$或者$O(k\log V)$。

上述过程甚至可以改成线段树分治后做堆合并。合并也是按上述方式暴力合并。

对于扩域子集第 K 小问题，按类似的方法做也可以做到$O(k\log k\log V)$。

【应用】树上第 K 小连通块

给出一棵$n$个点带正整数点权的树，求其上点权和第$k$小的连通块。$n\le 10^5$。

这个问题则只能用二分思想解决。

二分答案后问题转化为连通块计数。将连通块按其中深度最浅的点分类，就转化为树上堆合并的过程了。

QOJ 1548

【应用】购物计划

有$n$个商品，具有种类$a_i$和价值$c_i$。

现在要求购物，第$i$种的物品购买个数要在$[l_i, r_i]$之间。

求价值和第$k$小的代价。

$n, m, k\le 2\times 10^5$。

本题实际上是两个第 K 小问题的套娃。先在同一种类里做，然后对原问题做。

子问题

现在问题转化为大小在$[l, r]$范围内的子集第$k$小问题。

不妨将物品按价值排序，假设分别为$b_1, \ldots, b_t$。为了方便转移我们将末尾的连续下标记作一段区间，可以用$(x, y, z)$表示，其含义是我们选择的物品的末尾的极长下标连续段是$[x + 1, \ldots, x + y - 1]$，并且$b_x$是我们选择的第$z$个物品。其他信息可以忽略。初始状态$(1, l, 1)$。

转移有：

• $(x, y, z) \to (x + 1, y, z)$。
• $(x, y, z) \to (x + 1, y - 1, z + 1)$。
• 若$x = z = 1$且$y < r$，则有$(x, y, z) \to (x, y + 1, z)$。

容易证明引子的唯一性。

可以堆维护。

原问题

原问题即为扩域第 K 小问题。