不抛做法了，抛题目。
I
给定 n 个数，求和第 k 小的 m 元子集。
先升序，然后我们规定一个状态只移动极长前缀后的第一个元素（如果全是前缀就移动最后一个）。
状态记录目前在移动的元素和它相邻两个元素。则要么移动该元素，要么切换为移动上一个元素。
时间复杂度 O(nlogn+klogk)。
II
给定 n 个序列，要在每个序列中选恰好一个数，求和前 k 小的方案的和。
先将各个序列内部升序，一个状态先朴素地按照每个序列选第几个数记录。
那么我们有一个想法是移动最后一个不为 1 的元素，这样只需要记这个元素的位置。但这样会导致达成方式不唯一。
那么我们经过一个元素的时候一开始让它不是 1，但在最后一个操作的元素之前的元素可以改回 1（不妨认为只有 2 可以改成 1）。具体地，如果改成 1 了就转为操作下一个元素。
但这样会导致状态的答案的单调性消失，那我们按照前两个元素的差对序列之间的顺序进行排序即可。
时间复杂度 O(SlogS+klogk)，其中 S 是序列长度之和。
III
给定 n 个序列和参数 L,R，要在每个序列中选 [L,R] 个数，求和前 k 小的方案的和。
假如只有一个序列，只要在 I 的做法中将 R−L+1 个前缀都插入即可。当然也可以通过给前缀添加长度增长的转移来实现。
那么多个序列的情况，其实只需要把 II 和这个做法套起来即可。
时间复杂度 O(SlogS+klogk)，其中 S 是序列长度之和。
IV
给定 n 点 m 边，边权非负的有向图和 s,t，求 s 到 t 的第 k 短路长度。
考虑以 t 为根建出任意一棵最短路树。
那么我们一个方案就可以按照经过的顺序用一系列非树边来描述，其中一条边 (u,v) 的贡献是 w+du−dv，其中 du 是 u 到 t 的最短距离。并且一条边的终点是下一条边起点的祖先（认为自己是自己的祖先）。
那么我们考虑对这个边序列进行 k 小方案的构造。
那么无非就是替换最后一条边，或在最后插入一条边。
容易想到我们要在最后一条边的合法范围（也就是以倒数第二条边的终点的祖先为起点的边）内寻找 O(1) 个后继，或者直接插入新的范围内贡献最小的边。
这个我们可以有一个可持久化的线段树 / 平衡树结构，这样同时容易找到后继。
但我们实际上并不需要恰好找到后继，这就是我说 O(1) 的原因：如果使用结构比较常规的可持久化堆，能支持找到常数个可能的后继，也可以。
我们发现左偏树就可以实现。每次删除根结点后插入两个儿子即可。
另外注意到这个结构并不需要合并，因为我们可以在预处理的时候从父结点继承后插入新的边。
如果用线段树或平衡树，时间复杂度为 O(n+mlogn+klogk+klogn)。
如果用左偏树，时间复杂度为 O(n+mlogn+klogk)。
V
给定 n 个非负数 ai，定义一个排列 p 的权值是 ∑iaipi，求权值第 k 小的排列。
先降序，那么初始状态就是 pi=i。
显然操作应该是交换相邻的顺序对。
考虑从短到长依次确定每个后缀内的相对顺序。过程中，我们只把他们留在后缀内部。当前面的移进来的时候大概是一个插入的过程。
那可以想到一个状态 (x,y)，表示值 x 现在换到了 y，且我们只处理下标在 [x,n] 的后缀。
记 δi=ai+1−ai，那么往前拓展其实就是依次选择操作 δ 最小、次小……的位置，或者从那个位置开始按照一般的状态拓展。
这样这一部分我们其实也可以用可持久化的线段树平衡树或左偏树来实现。
但注意到在往后拓展的时候需要计算代价，可以直接用可持久化数组来实现。
时间复杂度 O(nlogn+klogk+klogn)。