题解：CF706D Vasiliy's Multiset（提供一种不用字典树的做法）

DPOI · 2025-06-30 20:56:03 · 题解

做法

首先，多重集的插入删除直接使用 multiset 实现即可。

再考虑到这种异或最大值的几乎是通用的解法就是拆位然后二进制从高往低贪心地考虑。

如何具体去去做呢？假设当前集合内有 (1000)_2,(1001)_2,(1011)_2,(0110)_2,(0001)_2，如果我们要查与 (0011)_2 异或后的最大值。

就可以这样做：\ 从高位往低位考虑，对于这种情况，我们就要先考虑是否存在 2^3 为 1 的元素？查询 2^3 位为 1 的元素也就是判断是否存在元素值域位于 (1000)_2 到 (1111)_2，这一步显然可以使用 lower_bound。

对于每一步都这样贪下去，就可以达到我们的答案了。

最终时间复杂度就是 O(q \log m \log n) 的，其中 m 是值域，最大一点点跑了 135ms。

CODE

#include<bits/stdc++.h>
using namespace std;
multiset<int>st;
const int M=30; 
bool check(int l,int r){
    auto it=st.lower_bound(l);
    return it!=st.end()&&*it<=r;
}
int main(){
    st.insert(0);
    int q;cin>>q;
    while(q--){
        char c;int x;cin>>c>>x;
        if(c=='+')st.insert(x);
        if(c=='-')st.erase(st.find(x));
        if(c=='?'){
            int tmp=0;
            for(int i=M-1;i>=0;--i){
                if((x>>i)&1){
                    if(!check(tmp,tmp+(1<<i)-1))
                        tmp+=(1<<i);
                }
                else{
                    if(check(tmp+(1<<i),tmp+(1<<(i+1))-1))
                        tmp+=(1<<i);
                }
            }
            cout<<(tmp^x)<<'\n';
        }
    }
}