【luogu CF1098D】Eels（结论）

Eels

题目链接：luogu CF1098D

题目大意

有一个可重集，每次操作会放进去一个数或者取出一个数。
然后每次操作完之后，问你对这个集合进行操作，每次选出两个数 a,b 加起来合并回去，直到集合中只剩一个数，要你最小化 2a<b 或 2b<a 的次数。
每次输出这个最小次数。

思路

有一个简单的贪心结论是每次选最小的两个合并。
感性理解就是你如果要贡献了，那迟早都要贡献，你这里加了说不定他就够大了就不一定在下一次贡献了。

接下来发现你这样这题好像还不能过。
于是考虑再推一点结论，发现它贡献的条件我们还没有用上。
于是考虑一下这个二倍，会发现一个什么问题，就是如果你某一次要贡献。
比如贡献的形式是 $x,y$，其中 $2x<y$，那你其实会发现这个 $y$ 是不可能是被合并出来的，它一定是原生的。

那如果它能被合出来 $y_1+y_2=y(y_1⩽y_2)$，那我们每次合最小的两个，那 $y_1,y_2$ 已经被合了 $x$ 还在，那一定有 $y_1⩽y_2⩽x$，那 $y_1+y_2⩽2x$ 即 $y⩽2x$ 与 $y>2x$ 矛盾。
也不难看出，当 $kx<y$ 为条件的时候，两个推出来的条件分别是 $y⩽2x$ 与 $y>kx$，也就是当 $k⩾2$ 的时候其实这个结论都成立，这也是这个条件成立的充要条件。

那这个说明什么，你如果要出现贡献，大的一定是原生的，而每次你都会合最小的两个，那要让大的是原生的也就是它是现在第二小的，而且比它大的里面不应该有非原生的。
因为有的话，就说明它肯定没有最小的二倍。
那最小的肯定就是原生的里面比他小的和。
那条件就是：（先把数组排序，在让 $su{m}_i=\sum _{x=1}^i{a}_x$）
$\sum _{i=1}^n[2su{m}_{i-1}<a_i]$

---

那我们要做的就是在插入数和删去数的过程中维护这个东西的值。
会发现问题在于每个地方都要判断一次，但是一个显然的事情是每一次是上次的两倍以上，那每次这个值都会翻倍，那就只会有至多 $\log$ 次贡献。
那你会发现如果你按最高位的存在来分（我们对于每个维护一个 set），那你会发现每一组至多只有一个贡献，那我们需要判断的次数也缩小到了 $\log$ 级别，就可以了。

代码

#include<set>
#include<cstdio>
#define ll long longusing namespace std;int n, ans;
multiset <int> s[36];
ll sum[36];int getk(int x) {int re = 0;while (x > 1) re++, x >>= 1;return re;
}int main() {scanf("%d", &n);while (n--) {char c = getchar(); while (c != '+' && c != '-') c = getchar();int x; scanf("%d", &x);int k = getk(x);if (c == '-') {s[k].erase(s[k].find(x));sum[k] -= x;}if (c == '+') {s[k].insert(x);sum[k] += x;}ll Sum = 0; ans = 0;for (int i = 0; i <= 30; i++)if (s[i].size()) {ans += s[i].size();if ((*s[i].begin()) > 2 * Sum) ans--;Sum += sum[i];}printf("%d\n", ans);} return 0;
}