Eels

題目鏈接：luogu CF1098D

題目大意

有一個(gè)可重集，每次操作會放進(jìn)去一個(gè)數(shù)或者取出一個(gè)數(shù)。
然后每次操作完之后，問你對這個(gè)集合進(jìn)行操作，每次選出兩個(gè)數(shù) a,b 加起來合并回去，直到集合中只剩一個(gè)數(shù)，要你最小化 2a<b 或 2b<a 的次數(shù)。
每次輸出這個(gè)最小次數(shù)。

思路

有一個(gè)簡單的貪心結(jié)論是每次選最小的兩個(gè)合并。
感性理解就是你如果要貢獻(xiàn)了，那遲早都要貢獻(xiàn)，你這里加了說不定他就夠大了就不一定在下一次貢獻(xiàn)了。

接下來發(fā)現(xiàn)你這樣這題好像還不能過。
于是考慮再推一點(diǎn)結(jié)論，發(fā)現(xiàn)它貢獻(xiàn)的條件我們還沒有用上。
于是考慮一下這個(gè)二倍，會發(fā)現(xiàn)一個(gè)什么問題，就是如果你某一次要貢獻(xiàn)。
比如貢獻(xiàn)的形式是 $x,y$，其中 $2x<y$，那你其實(shí)會發(fā)現(xiàn)這個(gè) $y$ 是不可能是被合并出來的，它一定是原生的。

那如果它能被合出來 $y_1+y_2=y(y_1?y_2)$，那我們每次合最小的兩個(gè)，那 $y_1,y_2$ 已經(jīng)被合了 $x$ 還在，那一定有 $y_1?y_2?x$，那 $y_1+y_2?2x$ 即 $y?2x$ 與 $y>2x$ 矛盾。
也不難看出，當(dāng) $kx<y$ 為條件的時(shí)候，兩個(gè)推出來的條件分別是 $y?2x$ 與 $y>kx$，也就是當(dāng) $k?2$ 的時(shí)候其實(shí)這個(gè)結(jié)論都成立，這也是這個(gè)條件成立的充要條件。

那這個(gè)說明什么，你如果要出現(xiàn)貢獻(xiàn)，大的一定是原生的，而每次你都會合最小的兩個(gè)，那要讓大的是原生的也就是它是現(xiàn)在第二小的，而且比它大的里面不應(yīng)該有非原生的。
因?yàn)橛械脑?#xff0c;就說明它肯定沒有最小的二倍。
那最小的肯定就是原生的里面比他小的和。
那條件就是：（先把數(shù)組排序，在讓 $su{m}_i=\sum _{x=1}^i{a}_x$）
$\sum _{i=1}^n[2su{m}_{i?1}<a_i]$

那我們要做的就是在插入數(shù)和刪去數(shù)的過程中維護(hù)這個(gè)東西的值。
會發(fā)現(xiàn)問題在于每個(gè)地方都要判斷一次，但是一個(gè)顯然的事情是每一次是上次的兩倍以上，那每次這個(gè)值都會翻倍，那就只會有至多 $\log$ 次貢獻(xiàn)。
那你會發(fā)現(xiàn)如果你按最高位的存在來分（我們對于每個(gè)維護(hù)一個(gè) set），那你會發(fā)現(xiàn)每一組至多只有一個(gè)貢獻(xiàn)，那我們需要判斷的次數(shù)也縮小到了 $\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;
}