题意：\(n\) 个数，对于所有大小在 \([L,R]\) 内的子集求和并排序，求前 \(k\) 小子集的信息。
排序，记数组为 \(a_{1,\cdots,n}\)。
先考虑 \(L=R\) 的情况。最小的子集一定是 \(a_{1,\cdots,L}\)，第二小则是将 \(a_L\) 改为 \(a_{L+1}\)，推广到更一般的情况——我们以 \([1,L]\) 作为初始状态，每次挑选一个前缀保留下来，剩余区间向后平移继续处理。
这一生成方法对应着一颗叶向树，且父亲的权值小于儿子的权值，因此前 \(k\) 小一定是包含根的一个连通块。
一个朴素的想法是用堆维护所有遍历到的状态，每次取出最小状态并将其所有儿子加入。但是儿子数量过多，复杂度会退化，考虑兄弟儿子表示法将树三度化，每次要么加入最优的儿子，要么加入一个未加入的最优的兄弟，合理地维护可以做到 \(O(n\log n)\)。
\(L<R\) 的情况是类似的，我们维护每个长度对应最值，再用一个堆维护不同长度谁最优就好了，复杂度仍然是 \(O(n\log n)\)。
CF1250I Show Must Go On
从大到小枚举 size，剩余部分与第一题处理方法类似。
P6646 [CCO2020] Shopping Plans
每一个种类分开讨论，剩余部分与第一题处理方法类似。
P2048 [NOI2010] 超级钢琴
比较简单的应用题，我们将一个结点定义为固定左端点，右端点为一段区间，每次取出最优的右端点将区间劈成两半塞入堆中即可，不需要三度化。
前 \(k\) 小子序列问题
题意：给定一个序列，求字典序前 \(k\) 小子序列的信息。
由于不好快速比较子序列的字典序大小，不能类似前面的题目用大堆合并全局信息。
我们仍然开 \(n\) 个堆，每个堆维护对应长度的子序列。信息记录最后一个位置以及其可以被替换成某个区间的元素，扩展方式有两种：类似上一题取出最小值劈开区间，或是在后面加入一个位置。
为了避免比较字典序，我们设计一种遍历方式：先采用第二种扩展方式，并转而考虑大小加一的堆，取完后继回溯时再采用第一种扩展方式，正确性显然。
复杂度 \(O(n\log n)\)。
P2483 【模板】k 短路 / [SDOI2010] 魔法猪学院
求出以 \(t\) 为根的最短路树，一条从 \(s\) 到 \(t\) 的路径可以被唯一地刻画为一个非树边序列（容易发现非树边序列相邻两条边 \(u,v\) 一定满足 \(u\) 的终点在 \(v\) 的起点的子树中）。
类似地，我们从状态空集开始，考察一个很朴素的生成方式：每次在非树边序列 pushback 一条新边。这一方法显然满足本文中算法要求的性质。
三度化后转移变为：
- 在最后一条边后接上最优的一条边：一定是一条到根路径连出的 delta 最小边。
- 将最后一条边替换成更大的一条：加入一条边后需要将其在这条路径上的后继加入决策。
使用可持久化可并堆维护，第一种转移平凡，第二种转移将其可并堆左右儿子加入决策即可，复杂度 \(O(m\log m)\)。
UOJ#53. 【UR #4】追击圣诞老人
注意到每个点的后继可以拆成不超过两条链，我们类似上一题从前往后扩展路径序列，信息记录可以参考超级钢琴一题，记录路径尾端，以及后继对应的链，每次取出链权值最小位置将链分成两部分重新加入堆即可，复杂度 1log。
标签：一条,浅谈,加入,短路,后继,问题,序列,复杂度 From： https://www.cnblogs.com/xiaoziyao/p/17477382.html