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