AtCoder Beginner Contest 308

G - Minimum Xor Pair Query

题意

给出一个初始为空的可重集合和三种操作。

1. 插入一个数；
2. 删除一个数；
3. 输出集合内任取两数异或的最小值。

题解

一个重要的性质是：若 $x<y<z$，则 $\min(x\oplus y,y\oplus z)<x\oplus z$。

证明如下：我们记 $x$ 与 $z$ 的 $k+1$ 及更高的位相同，第 $k$ 位不同。（即从高到低比较各位，直到出现第一位不同）那么 $x\oplus z\geq 2^k$。而 $y$ 介于 $x$ 和 $z$ 之间，所以它的 $k+1$ 及更高的位也和它们相同。而它的第 $k$ 位与 $x$ 或 $z$ 相同。它们的异或是小于 $2^k$ 的。证毕。

所以，我们只需要维护相邻的数的异或值即可。可以用map实现。

代码

#include <bits/stdc++.h>
using namespace std;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    map<int,int> mp,ans;
    int q;cin>>q;
    while(q--)
    {
        int op;cin>>op;
        if(op==1)
        {
            int x;cin>>x;
            int y=-1,z=-1;
            if(!mp.empty())
            {
                auto it=mp.upper_bound(x);
                if(it!=mp.end())
                {
                    y=it->first;
                    ans[y^x]++;
                }
                if(it!=mp.begin())
                {
                    it--;
                    z=it->first;
                    ans[z^x]++;
                }
                if(y!=-1&&z!=-1)
                {
                    ans[y^z]--;
                    if(!ans[y^z]) ans.erase(y^z);
                }
            }
            mp[x]++;
        }
        else if(op==2)
        {
            int x;cin>>x;
            int y=-1,z=-1;
            mp[x]--;
            if(!mp[x]) mp.erase(x);
            if(!mp.empty())
            {
                auto it=mp.upper_bound(x);
                if(it!=mp.end())
                {
                    y=it->first;
                    ans[y^x]--;
                    if(!ans[y^x]) ans.erase(y^x);
                }
                if(it!=mp.begin())
                {
                    it--;
                    z=it->first;
                    ans[z^x]--;
                    if(!ans[z^x]) ans.erase(z^x);
                }
                if(y!=-1&&z!=-1)
                {
                    ans[y^z]++;
                }
            }                        
        }
        else
        {
            auto it=ans.begin();
            cout<<it->first<<'\n';
        }
    }
    return 0;
}