CF706D Vasiliy's Multiset 题解

黑影洞人 · 2022-09-14 18:59:07 · 题解

01Trie 模板题

题意：支持插入，删除，求任意两个数的最大异或值。

第一眼想到了线性基，但是发现线性基不支持指定两个数。

于是我们想到了 01Trie 来维护。

插入操作：

获取到每一位的情况后，依次往下找，如果那个点被选过了，那么往下走，否则就新开一个节点，每个节点用计数器统计一下覆盖的次数，方便后面的删除操作。

如果完全插入了，那么就在最后的节点标记一下值，避免反复查找。

void insert(int x){
    int u=1;
    for(int i=M;i>=0;i--){
        int v=x>>i&1ll;
        if(!ch[u][v])ch[u][v]=++cnt;
        u=ch[u][v]; 
        num[u]++;
    }
    val[u]=x;
}

删除操作：

按位依次往下走，然后把点经过的次数减去 1 即可。

void del(int x){
    int u=1;
    for(int i=M;i>=0;i--){
        int v=x>>i&1ll;
        u=ch[u][v]; 
        num[u]--;
    }
}

查询操作：

按位向下找，如果能取反就取反，否则才取正。

int querymax(int x){
    int u=1;
    for(int i=M;i>=0;i--){
        int v=x>>i&1ll;
        if(ch[u][v^1]&&num[ch[u][v^1]])u=ch[u][v^1];
        else u=ch[u][v];
    }
    return x^val[u];
}

完整代码：

#include<cstdio>
#include<algorithm>
#define N 114514
#define M 63
#define int long long
using namespace std;
int n;
struct trie{
    int ch[N*M][2],cnt=1,num[N*M],val[N*M];
    void insert(int x){
        int u=1;
        for(int i=M;i>=0;i--){
            int v=x>>i&1ll;
            if(!ch[u][v])ch[u][v]=++cnt;
            u=ch[u][v]; 
            num[u]++;
        }
        val[u]=x;
    }
    void del(int x){
        int u=1;
        for(int i=M;i>=0;i--){
            int v=x>>i&1ll;
            u=ch[u][v]; 
            num[u]--;
        }
    }
    int querymax(int x){
        int u=1;
        for(int i=M;i>=0;i--){
            int v=x>>i&1ll;
            if(ch[u][v^1]&&num[ch[u][v^1]])u=ch[u][v^1];
            else u=ch[u][v];
        }
        return x^val[u];
    }
}st;
signed main(){
    scanf("%lld",&n);
    st.insert(0);
    while(n--){
        char s[12];
        int a;
        scanf("%s%lld",s,&a);
        if(s[0]=='+')st.insert(a);
        else if(s[0]=='-')st.del(a);
        else printf("%lld\n",st.querymax(a));
    }
    return 0;
}