题目简述：对一个非空正整数（可重）集合$S$，从中选出两个元素$a, b (a leq b)$，将他们从$S$中删除并将$a+b$加入$S$，重复这个操作直到$S$中只剩下一个元素为止，称为一次【竞技】。若一次操作中$a leq b leq 2a$，则称这次操作是【危险的】。一次竞技的【危险值】为其中【危险的】操作的次数。定义这个集合$S$的【危险值】（记作$ ext{danger}(S)$）为：所有可能的竞技的【危险值】的最大值。设一个集合$S$初始为空集，维护以下操作：
1. 插入一个数$1 leq x leq 10^9$。
2. 删除一个（已有的）数$1 leq x leq 10^9$。
每次操作后，计算$ ext{danger}(S)$。
解：code
对$x in S$，定义$S$中比$x$小的数之和为
$$ f(x) = sum_{a in S, a < x} a. $$
定义$x$的等级为
$$ g(x) = max_{a in S, a < x} { g(a) } + [2f(x)<x], $$
特别地，$max emptyset = 0$。
令$S$中的最高等级为
$$t = max_{x in S} { g(x) }. $$
观察0：若$x < y$，则$ g(x) leq g(y) leq g(x)+1 $。
观察1：$ ext{danger}(S)=|S|-t$。
证明：
先证$ ext{danger}(S) leq |S|-t$。令$T = { (x, g(x)): x in S }$，则$S$中的一次操作
【从$S$中取出两个元素$a$和$b$，并把$a+b$插入$S$。】
可对应为$T$的一次操作：
【从$T$中取出两个元素$(a, x)$和$(b, y)$，并把$(a+b, max{x,y})$插入$T$。】
于是$S$的一次竞技，可对应$T$的一次竞技。
注意到，若$T$中的一次操作有$x = y$，则称这次操作是【不安全的】。$S$的任何一次不【危险的】操作，在$T$中都不是【不安全的】。$T$中一次竞技的【不安全值】为其中【不安全的】操作的次数。定义$T$的【不安全值】为所有可能的竞技的不安全值的最大值，记作$ ext{unsafe}(T)$。则显然有$ ext{danger}(S) leq ext{unsafe}(T)$。
另一方面，$T$的任意一个可能的竞技中，都会导致竞技的结果剩下$(sum_{a in S} a, max_{a in S} { g(a) })$，又至少有$t-1$次操作有$x eq y$，从而$ ext{unsafe}(T) leq (|T|-1)-(t-1) = |T|-t$，即$ ext{danger}(S) leq |S|-t$。
再证$ ext{danger}(S) geq |S|-t$。我们只需给出一个竞技策略，即每次操作是从$S$中取出最小的两个元素$a$和$b$，并把$a+b$插入$S$。假设在某次操作$a$和$b$（$a leq b$）的不【危险的】，即$2a<b$，则$b$不曾被合并过（或者说$b$是$S$的原始元素），不然设$b = c+d$其中$c leq d$，则$d geq b/2 > a$，这说明$d$在$a$之前参与了某次合并操作，这与我们的竞技策略矛盾。这个竞技策略会导致，每种不同等级的元素中，恰好有一个（这个等级中某个最小的元素）参与了不【危险的】操作，从而这个竞技的【危险值】为$|S|-t$。故$ ext{danger}(S) geq |S|-t$。
综上，有$ ext{danger}(S)=|S|-t$。
QED
因此，我们把$ ext{danger}(S)$的计算转化为求$S$中元素的最高等级$t$。
观察2：$g(x) leq log_2 x + 1$，从而$t leq log_2 V+1$，其中$V = max_{x in S} {x}$。（数学归纳法）
我们将元素的取值范围划分为$[1, 2), [2, 4), [4, 8), dots, [2^{k}, 2^{k+1}), dots, [2^{29}, 2^{30})$。
观察3：在$[2^{k}, 2^{k+1})$范围内的至多存在一个$x in [2^{k}, 2^{k+1})$，使得$g(y) < g(x)$对任意$y < x$成立。若存在这样的$x$，则$x$必为$[2^{k}, 2^{k+1})$中的最小值，且$2f(x)<x$。$t$等于满足这个条件的$x$的个数。
于是对每个$k = 0, 1, 2, dots, 29$，维护容器$H[k]$，在插入（或删除）一个元素$x$时，若$x in [2^{k}, 2^{k+1})$，则把$x$插入（或删除自）$H[k]$。对计算$ ext{danger}(S)$，只需统计满足【观察3】的条件的$x$的个数。可用multiset来维护$H[k]$。
一共需要维护$O(log V)$个multiset，从而时间复杂度为$O(Q log Q log V)$，其中$Q$为询问次数，$V$为所有元素的最大值。