关于一类求前 k 优解的问题

当我们要求某个问题的前 \(k\) 优局面的时候，我们可以考虑用堆贪心来实现。其实这个堆贪心本质上是在做 dijkstra 一样的东西。

我们考虑对于每个局面（状态）构造一个转移 \(trans(S)\)，它导出 \(O(1)\) 个转移，且满足：

• 若 \(S\) 转移到 \(T\)，则权值满足单调性：\(val(T) \ge val(S)\)，也就是只会转移到比自己劣的状态。

• 对于每个可能的状态，有且仅有一种从初始局面 \(I\) 转移到它的路径。（所以转移边构成外向树的关系）。

显然当我们建立了这样一个结构的时候，就可以直接用堆在 \(O(k\log k)\) 的时间内求出前 \(k\) 个解。

当然，这里有一个隐含条件，就是我们能够用 \(O(1)\) 个信息来确定这个局面的后续转移。（我们不关心局面到底长什么样子，只需要维护能让它转移的信息，以及它本身的价值就够了）。

这样讲比较抽象，我们来考虑一个很经典的问题：

P1：给出一个多重集 \(A\)，全部由非负整数构成，求它的前 \(k\) 小子集的大小（大小定义为元素的和）。

我们考虑把 \(A\) 排序，然后令 \(pre\) 是前缀和数组，状态里记录一个 \(pos\)，表示这个子集里下标最大的元素。

我们初始的时候把所有的 \(\{pre_i,i\}\) 这样的状态加入堆中。对于一个 \(\{sum,x\}\) 的状态，它的转移就是 \(\{sum+a_{x+1}-a_x,x+1\}\)。

这个转移的构造符合上述的所有条件，然后就能 \(O(k\log k)\) 解出。

这其实就是我们上述思想的最基本应用。

P2：给出 \(n\) 个正整数数组，定义一种方案是从每个数组里选恰好一个，其代价为选出的所有数之和。求前 \(k\) 优秀方案的代价。其中 \(n,k,\sum len \le 10^5\)。(洛谷P2541）

考虑套用我们的模型，则初始状态显然是选每个数组里最小的那个，而拓展就是选一个数组，让它选的数变大。

因此我们不妨按照把每个数组排序，维护 \(n\) 个指针，第 \(i\) 个指针表示说第 \(i\) 个数组选的是哪个数。转移的时候我们可以选一个指针，让它指向下一位。

这样有个问题，就是一个状态会被走到多次，因为你每次可以随便动一个指针，势必会算重。

所以我们就考虑从前往后按顺序动指针，确定了第 \(i\) 个人的指针是谁以后，我们再去确定第 \(i+1\) 个人的指针。

这样，我们可以设计我们的状态维护 \(\{sum,pos,x\}\)，表示说我们当前在动第 \(pos\) 个人的指针，且它指向第 \(x\) 个数。

如何转移？显然有一种是转移到 \(\{sum',pos,x+1\}\)，还有一种情况是说我们确定了第 \(pos\) 个人，最终就是指向 \(x+1\)，那就应该转移到 \(\{sum,pos+1,1\}\)。

但是这样会有问题：我们还是会把一个状态算重多次。原理就在于会有人的指针指向 \(1\)。

什么意思？我们用一个元组来描述每个位置的指针，考虑 \((2,1,1,1)\) 这个局面，则我们在 \(pos=2,x=1\)，\(pos=3,x=1\)，\(pos=4,x=1\) 的时候都会把它算进去，这怎么办？

我们引入撤销的机制：首先我们强制要求所有状态的 \(x\ge 2\)，然后当我们的 \(x=2\) 的时候，可以把 \(pos\) 这个数组，从选第 \(2\) 个数撤销到选第一个数；然后移动到 \(pos+1\)，将其从第一个数变成选第二个数。

引入这个撤销后，我们初始压入的状态应该是 \(\{pos,2\}\)。这样每个状态终于是唯一被走到了。(除了最优解，这点需要特判）。

但是又出现了问题：在撤销的过程中，我们可能会出现边权为负的转移。

这个时候解决方案已经很显然了：对于只有一个数的数组，它的选法是选死的；对于至少有两个数的数组，按照 \(a_2 - a_1\) 升序排序。这样即使在撤销操作中，我们也能保证非负转移。

这样，此题也在 \(O(k\log k)\) 的时间内解决。

当引入了撤销（反悔）机制后，其实这个模型已经比较完善了。

P3： 在 P2 的基础上，我们修改对每个数组的约束，给出 \([L_i,R_i]\) 表示需要从第 \(i\) 个数组里选出数量在 \([L_i,R_i]\) 之间个数的若干个数；问此时的前 \(k\) 优方案。(洛谷P6646)

先来考虑单个数组的情况，我们会发现可以类似 P1 的方式，在 \(O(k\log k)\) 的时间内解决。

实际上我们对每个数组，用这个堆贪心的模型建立了一个数据结构：它支持在 \(O(k\log k)\) 的时间内求出这个数组的前 \(k\) 优秀解。

然后我们利用这个“黑盒”，套用 P2 的做法，则在 \(O(k\log k)\) 的时间内求出了答案。

代码

通过上面的几道例题，其实这个模型已经很完备了，直到我今天又做到了这个题：

P4： 给出一个非负整数数组 \(a\)，对于长度为 \(n\) 的排列 \(p\)，定义其代价为 \(\sum a_i\times p_i\)。求代价前 \(k\) 小的排列的代价，其中 \(n,k\le 10^5\)。

不妨假设 \(a_i\) 降序，然后最优解就是 \(p_i = i\)。考虑再次基础上调整拓展。很容易想到拓展方式就是交换相邻的升序对。

考虑让每个排列被唯一得到：于是从后往前考虑每个人，然后让它往后 swap 若干步。也就是我们按照 \(i\) 从小到大确定最后 \(i\) 个人的相对次序（保证他们全部在最后 \(i\) 个位置）。

这样的话就需要记录 \(p\) 和 \(x\)，表示我们把现在轮到从前往后第 \(p\) 个人一直向前 swap，搞到了第 \(x\) 个位置，这里 \(x\gt p\)。于是初始状态就是枚举所有的 \(i\)，然后第一步交换 \(i\) 和 \(i+1\)，之后的全部保持不动，然后压入 \(p=i,x=i+1\)。

这样的话，第一种转移很显然就是 \(p,x \rightarrow p,x+1\)。当我们考虑往前的时候，出现了问题。

第二种转移，我们假设位置 \(p-1\) 的人会往后 swap，则转移到 \(\{p-1,p\}\)，这是很正确的。但是如果它不动，注意这是第三种可能的转移，我们发现此时是套不了撤销模型的：因为不能保证这里交换相邻的代价比更靠前交换相邻的代价小。同时我们也无法按照这个东西排序后再去转移，不然前面的那些转移都完全无法去做。

所以这题的特殊性质在于我们无法交换扫描的顺序了，因此这个问题会比之前的这部分要严格强。但我们其实也是能做的。

考虑定义一个 \(pre\) 变量，它原本表示我们当前只考虑了 \(\gt pre\) 的位置，剩余的前缀都保持 \(p_i=i\)；因此原本 \(pre\) 就是 \(p-1\) 不用记录。现在，我们定义 \(f_i\) 表示 \(a_{i+1} - a_i\) 的值（也就是在这里第一次 swap 的代价），则我们的第三种转移，可以改成找到 \(f_{[1,pre) }\) 中的最小值位置 \(d\)，然后交换 \(d\) 和 \(d+1\)，然后我们转移到 \(p = d,x = d+1\)，且 pre 不变的这样一个状态。

也就是我们开始允许 \(pre \ge p\)。这样的意义是什么？当 \(pre=p-1\) 的时候，就是我们本来就有的正常状态，正常做就好了；当 \(pre \ge p\) 的时候，意味着我们在 \(1\sim pre\) 这些位置里，其实只有 \(p,p+1\) 这一处交换，且我们允许撤销这次交换，然后找一个更大的 \(f\) 的位置，交换他们。同时我们也允许把这个状态变成一个正常的状态：它支持一般状态的那三种转移，且一旦这样做了，\(pre\) 在后续状态里立马就会成为 \(p-1\)。

这样我们需要对一个前缀查询某个 \(f_x\) 的后继位置（按照 \(f\) 排序后），可以在主席树上二分解决。

最后我们发现我们其实是需要知道序列的具体值的，也就是我们要把整个序列存下来。但其实也不需要全存，因为每次拓展只有 \(O(1)\) 的交换，所以维护可持久化数组即可。

这样我们还是在 \(O(k\log k)\) 的时间内解决了这个问题，不过此时的常数非常巨大了。

代码