Topk问题
前$k$小和卡组问题
题目：假设现在有$g$个非空卡组，第$i$个卡组中有$c_i$个数。现在希望从每个卡组中各取一个数，组成一个新的卡组，记卡组的权重为卡组中所有元素的和，问权重前$k$小的卡组的权重分别是多少。数据范围模满足$1\leq g\leq 10^6,\sum_{i=1}^gc_i\leq 10^6,k\leq 10^6,\prod_{i=1}^gc_i\geq k$。
对于大小为$1$的卡组，我们无需过多考虑，因为它的选择是唯一的。我们可以假设所有的卡组的大小都至少为$2$。
这道题有非常有趣的做法。我们先将所有卡组中的数按从小到大进行排序好。之后很显然最小的权重是通过每个卡组中都取最小的数得到的。
我们可以定义状态为三元组：$(sum,gId,cId)$。其含义为仅处理了$1,\ldots,gId$这些卡组，后面的$gId+1,\ldots,g$卡组中都选择第一个数（最小的那个）。且第$gId$卡组中我们取的数是第$cId$个数。
接下来我们考虑它的转移：
- 如果$cId<c_{gId}$，那么我们可以从第$gId$组中选择第$cId+1$个元素，于是得到转移$(sum+?,gId,cId+1)$。
- 如果$gId<g\land cId>1$，那么我们可以停止处理$gId$卡组，开始从$gId+1$中选择第二个元素，于是得到转移$(sum+?,gId+1,2)$。
- 如果$gId<g\land cId=2$，那么很显然上一次操作是将$gId$卡组的第一个元素替换为第二个，我们可以回退上次操作，停止处理$gId$卡组，开始从$gId+1$中选择第二个元素，于是得到转移$(sum+?,gId+1,2)$。
从初始状态出发（所有卡组都选第一个数），可以保证每个状态都会被遍历，且仅遍历一次。可以使用构造性证明每个状态都会被遍历，且每个状态的父状态都是唯一确定的。（这里的状态是指真实构建的结果，而非三元组，同一个三元组可能被多次处理，但是每一次处理都对应不同的结果）。
为了使贪心算法生效，我们需要保证父亲状态的权重一定不超过孩子状态。可以发现除了最后一个转移外，其余几个转移都会使得下一个状态的$sum$增大（或者保持不变），对于最后一个转移，我们可以提前将所有组按照次小值和最小值之间的差从小到大排序，并按照这个顺序重新对卡组进行编号。这样做后，可以发现所有状态转移出的新的状态的$sum$都不会减少。
于是我们每处理一个数，都可能会新增$3$个状态，总的处理的状态数不会超过$k$，因此总的时间复杂度为$O(g\log_2g+\sum_{i=1}^gc_i\log_2c_i+3k\log_2{3k})$。
提供几道题目：
前$k$小和问题
题目1：给定一个多重集合$S$，$S$初始是空集。之后$n$个请求，请求分三类：
- 向集合插入一个数$x_i$
- 从集合删除一个数$y_i$
- 查询集合中最小的$k_i$个元素的和
这道题可以直接用平衡树解决。$O(n\log_2n)$可以解决。
提供一道题目。