提供一个比较好写的 1 log 做法。

题意

有 nn 个桶，容积无限大，知道每个桶初始有 aia_i 千克的水。现在有一个桶恰额外含有 0.1790.179 千克的毒药，进行任意次如下两种操作：

  1. 选择两个桶 AA，桶 BB，比较重量，知道哪边重或一样重；
  2. 选择桶 AA，桶 BB，从 AA 桶中倒 xx 千克水（xx 不一定是整数）进入 BB 桶，要求：
    ※ AA 桶必须不含毒药；
    ※ AA 桶至少要含有 xx 千克的水。

判断是否能唯一确定哪个桶装着毒药，输出 Yes/No。

现在会进行 qq 次修改，每次的修改为增加一个初始水量为 bb 的桶，或删去一个初始水量为 bb 的桶（保证存在），修改持续。
每次修改后，输出 Yes/No，代表当前情况是否能判断哪个桶装着毒药。

n,q≤2×105,ai,b≤106n,q\le 2\times 10^5, a_i,b\le10^6。

解法

注意到操作 1 只有两个桶装的水是同样重的才有用（要不然有没有毒药不会影响结果），而且操作 2 选择的桶 AA 一定确定没有毒药。

则初始一定是选择两个装的水都是 kk 千克的桶，然后比较，如果有毒药就结束了，我们考虑它们重量一样，也就是没有毒药的情况。

这时候我们可以自由支配的水量是 2k2k，记作 LL。
我们发现所有的操作都可以归为两种：

  1. 选择 ai≤La_i\le L，让 L←L+aiL\leftarrow L+a_i。（也就是用 LL 获得一个装了 aia_i 水的桶去比）
  2. 选择 ai+L≥aja_i+L\ge a_j（ii 和 jj 都未确定），让 L←L+ai+ajL\leftarrow L+a_i+a_j。（也就是把 aj−aia_j-a_i 的水倒进桶 ii 里面，然后 ii 和 jj 再去比较）

初始令 L=0L=0，一开始找到两个装的水都是 kk 千克的桶的过程可以用操作 2 来描述，所以我们抛弃第一步，直接从 L=0L=0，未确认任何桶开始的初始条件来解决这个问题，不断进行操作，如果最后能确定大于等于 n−1n-1 个桶没有毒药，那么就应该输出 Yes（因为最后一个桶可以排除法确定）。

用值域倍增分块加速这个过程。

把值域按照 [2k,2k+1)[2^k,2^{k+1}) 分成 O(log⁡ai)O(\log a_i) 块。
我们可以发现一个性质，如果我们确定了某一块内任意一个桶没有毒药，那么就可以确定一整块所有的桶是否有毒药。

我们证明这个结论：
假设当前这个数是 aia_i，在块 [2k,2k+1)[2^k,2^{k+1}) 中：

  1. 如果这一个桶是由操作 1 确定的，那么此时 L′=L+ai≥2ai≥2k+1L' = L + a_i \ge 2a_i \ge 2^{k+1}，所以 L′L' 比这一个块内所有数都大，自然可以用操作 1 确定这一块里面每个桶。
  2. 如果这一个桶是由操作 2 确定的，L′=L+ai+aj≥2ai≥2k+1L' = L + a_i + a_j \ge 2a_i \ge 2^{k+1}，同理得证。

对于每个块 [2k,2k+1)[2^k,2^{k+1})，用 multiset 可以在 O(log⁡ai)O(\log a_i) 时间复杂度内轻易维护每块内的数，和每块两两之间的差。

我们从小到大遍历每一块，如果这一块存在一个能被确定，就把之前所有没确定的都确定，总和加入 LL 中。

存在一个在 SS 内能被确定的等价条件是：L≥min⁡i∈S(ai)L\ge \displaystyle\min_{i\in S}(a_i) 或 L≥min⁡i∈S,j 未被确定(∣ai−aj∣)L\ge \displaystyle\min_{i\in S, j\text{ 未被确定}}(|a_i-a_j|)。
第一个就是当前块内的最小值，已经用 multiset 维护了。
第二个条件只需要维护相邻块最大值和最小值之间的差和块内的差取最小值即可，尽管下一块可能是一个空块，也就是相邻的下一个数在下下块，但无需考虑这个的差，因为这个的差一定比 2k+12^{k+1} 大，一定不优，只需要上一块和下一块的差就行了。值得注意的是，如果上一块已经被确定了，那么不应考虑上一块的贡献。

这样遍历一遍，维护当前确定到了第几块，每次成功确定了这一块就把前面的都加入贡献，维护我们确定了多少个数就能解决本题。

代码很好写：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include<bits/stdc++.h>
using namespace std;

using ll=long long;

struct Bucket{
    multiset<int> diff;
    multiset<int> st;
    ll sum;
    void insert(int x){
        sum += x;
        auto it = st.insert(x);
        if(it != st.begin())diff.insert(*it - *prev(it));
        if(next(it) != st.end())diff.insert(*next(it) - *it);
        if(it != st.begin() && next(it) != st.end())
            diff.erase(diff.find(*next(it) - *prev(it)));
    }
    void erase(int x){
        auto it = st.find(x);
        if(it != st.begin())diff.erase(diff.find(*it - *prev(it)));
        if(next(it) != st.end())diff.erase(diff.find(*next(it) - *it));
        if(it != st.begin() && next(it) != st.end())
            diff.insert(*next(it) - *prev(it));
        st.erase(it);
        sum -= x;
    }
    bool empty(){return st.empty();}
}b[21];

void insert(int x){b[__lg(x)].insert(x);}
void erase(int x){b[__lg(x)].erase(x);}

int n,q;
void solve(){
    ll sum = 0;
    int nowb = 0,cnt = 0;

    for(int i=0;i<=19;i++){
        if(b[i].empty())continue;
        int mindiff = b[i].diff.size() ? *b[i].diff.begin() : 1e9; 
        mindiff = min(mindiff, *b[i].st.begin());
        
        if(i && b[i-1].st.size() && nowb<=i-1)mindiff = min(mindiff, *b[i].st.begin());
        if(i!=19 && b[i+1].st.size())mindiff = min(mindiff, *b[i+1].st.begin() - *b[i].st.rbegin());
        if(mindiff <= sum){ 
            for(;nowb<=i;++nowb){
                sum+=b[nowb].sum,cnt+=b[nowb].st.size();
            }
        }
    }
    
    if(cnt >= n-1)cout<<"Yes\n";
    else cout<<"No\n";
}

int main(){
    ios::sync_with_stdio(0);cin.tie(0);

    cin>>n>>q;
    for(int i=1;i<=n;i++){
        int x;cin>>x;
        insert(x);
    }

    solve();
    while(q--){
        string op; int x;
        cin>>op>>x;
        if(op[0]=='-')erase(x),--n;
        else          insert(x),++n;
        solve();
    }
    return 0;
}