字典树（类似一种贪心）

字典树

codeforces 706D

#include<stdio.h>
#include<bits/stdc++.h>
#include<algorithm>
using namespace std;
int ch[3200000][2];
int n,x,tot=1,ans,sum[3000000];
char s;
void add(int x)
{
    int now=1;
    for(int i=30; i>=0; i--)
    {
        if(x&(1<<i))
        {
            if(!ch[now][1])
                ch[now][1]=++tot;
            now=ch[now][1];
            sum[now]++;
        }
        else
        {
            if(!ch[now][0])
                ch[now][0]=++tot;
            now=ch[now][0];
            sum[now]++;
        }
    }
}
void delect(int x)
{
    int now=1;
    for(int i=30; i>=0; i--)
    {
        if(x&(1<<i))
        {
//            if(!ch[now][1])
//                ch[now][1]=++tot;
            now=ch[now][1];
            sum[now]--;
        }
        else
        {
            now=ch[now][0];
            sum[now]--;
        }
    }
}
//这个要强制记住么，还是啥？我自己可以构造么，我不知道
void query(int x)
{
    int now=1;
    for(int i=30; i>=0; i--)
    {
        if(x&(1<<i))
        {
            if(sum[ch[now][0]])
            {
                ans+=(1<<i);
                now=ch[now][0];

            }
            else
                now=ch[now][1];
        }
        else
        {

            if(sum[ch[now][1]])
            {
                ans+=(1<<i);
                now=ch[now][1];

            }
            else
                now=ch[now][0];
        }
    }
}
//类似一种贪心算法，记住他
int main()
{
    cin>>n;
    add(0);
    while(n--)
    {
        cin>>s>>x;
        if(s=='+')
        {
            add(x);
        }
        if(s=='-')
            delect(x);
        if(s=='?')
        {
            ans=0;
            query(x);
            printf("%d\n",ans);
        }
    }
    return 0;
}