题解归档 - cf706D

本文由 cf-code 本地题解库自动归档；公开内容以本地 AC/验证版本为准。

• 本地编号：cf706D
• 本地来源：problems/cf706D/idea.md
• 题目链接：https://codeforces.com/contest/706/problem/D
• 原始标题：706D Vasiliy's Multiset

思路

706D Vasiliy's Multiset

题意

维护一个多重集合 (A)，初始含整数 (0)。(q) 次操作：

• + x：加入 (x)
• - x：删除一个 (x)（保证存在）
• ? x：求 (\max_{y \in A} (x \oplus y))

保证至少有一次 ? 查询。

思路

01 字典树（二进制 Trie）：按位从高到低（本题 (x \le 10^9)，用 30 位足够）建树。

• 每个节点存 ch[0/1] 与 cnt（经过该节点的元素个数，支持重复与删除）。
• ins(x)：沿 (x) 的二进制路径下行，沿途 cnt++。
• del(x)：同路径 cnt--。
• ask(x)：贪心——第 (i) 位优先走与 (x_i) 相反 的子节点（若 cnt>0），否则走相同位；异或贡献累加到答案。

初始 ins(0) 满足题面「0 始终在集合中」。

模板

二进制 Trie + 可删多重集，见 lib/数据结构(字典树).cpp。

void ins(ll x){
    cur=rt;
    for(i=wd;i>=0;i--){
        bit=(x>>i)&1;
        if(!ch[cur][bit]) ch[cur][bit]=++ptr;
        cur=ch[cur][bit];
        cnt[cur]++;
    }
}
ll ask(ll x){
    cur=rt,ans=0;
    for(i=wd;i>=0;i--){
        bit=(x>>i)&1;
        want=bit^1;
        if(ch[cur][want] and cnt[ch[cur][want]]){
            cur=ch[cur][want];
            ans|=(1ll<<i);
        }
        else cur=ch[cur][bit];
    }
    return ans;
}

复杂度

• 单次操作：(O(\log V))，(V \approx 2^{30})
• 空间：(O(q \cdot \log V)) 节点（删除不回收节点，只减 cnt）

验证

• 样例：✅
• 对拍：500 组随机增删查 → stress.py 通过（本地 WSL）

结果

• CF 提交 #377696955 — AC
• 模板已沉淀：lib/数据结构(字典树).cpp

代码

来源：problems/cf706D/solution.cpp

/* Author: likely
 * Time: 2026-06-08 02:40:11
**/
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxn=8000005,wd=30;
ll ch[maxn+5][2],cnt[maxn+5],ptr,rt,q,i,j,k,x,bit,want,cur,ans;
char op;
void ins(ll x){
    cur=rt;
    for(i=wd;i>=0;i--){
        bit=(x>>i)&1;
        if(!ch[cur][bit]) ch[cur][bit]=++ptr;
        cur=ch[cur][bit];
        cnt[cur]++;
    }
}
void del(ll x){
    cur=rt;
    for(i=wd;i>=0;i--){
        bit=(x>>i)&1;
        cur=ch[cur][bit];
        cnt[cur]--;
    }
}
ll ask(ll x){
    cur=rt,ans=0;
    for(i=wd;i>=0;i--){
        bit=(x>>i)&1;
        want=bit^1;
        if(ch[cur][want] and cnt[ch[cur][want]]){
            cur=ch[cur][want];
            ans|=(1ll<<i);
        }
        else cur=ch[cur][bit];
    }
    return ans;
}
int main(){
    cin>>q;
    ins(0);
    while(q--){
        cin>>op>>x;
        if(op=='+') ins(x);
        else if(op=='-') del(x);
        else cout<<ask(x)<<"\n";
    }
    return 0;
}