Codeforces Round #367 (Div. 2) D. Vasiliy’s Multiset 二进制树、Trie

Source

Codeforces Round #367 (Div. 2)

My Solution

二进制树、Trie

用一个二进制树(字典树的一种特殊化)来储存

child[x][k] 表示以x为父节点， k 为边， 的子节点

sz[x]表示这个节点的值, 值为0的时候节点不存在

查询的时候， 从根开始走， 尽量去走 和 val 的当前二进制为不相等的节点， 此时的二进制异或为 1 ，  k = ((val >> i) & 1) ^ 1, res ^= 1 << i;

如果没有再走二进制为相等的节点 if(!sz[child[x][k]]) k ^= 1, res ^= 1 << i;

走到不能再走的时候， res就是答案了

复杂度 O(q * log (2^31))

#include 
#include 
#include 
using namespace std;
typedef long long LL;
const int maxn = 2*1e5 + 8;

int child[maxn*31][2], sz[maxn*31], sum = 1;
inline void modify(int val, int d)
{
    int k, x = 1;
    for(int i = 30; i >= 0; i--){
        k = (val >> i) & 1;
        if(!child[x][k]) child[x][k] = ++sum;
        sz[x] += d;
        x = child[x][k];
    }
    sz[x] += d;
}
inline int query(int val)
{
    int k, x = 1, res = 0;
    for(int i = 30; i >= 0; i--){
        k = ((val >> i) & 1) ^ 1, res ^= 1 << i;
        if(!sz[child[x][k]]) k ^= 1, res ^= 1 << i; x = child[x][k]; } return res; } int main() { #ifdef LOCAL freopen("d.txt", "r", stdin); //freopen("o.txt", "w", stdout); int T = 1; while(T--){ #endif // LOCAL ios::sync_with_stdio(false); cin.tie(0); int q, val; char ch; cin >> q;
    modify(0, 1);
    //^^^^^^       WA5 第一个操作就是 ? 1 !!!!!! You are given q queries and a multiset A, initially containing only integer 0.
    while(q--){
        cin >> ch >> val;
        if(ch == '+') modify(val, 1);
        else if(ch == '-') modify(val, -1);
        else cout << query(val) << endl;
    }


    #ifdef LOCAL
    cout << endl;
    }
    #endif // LOCAL
    return 0;
}

非特殊说明，本博所有文章均为博主原创，未经许可不得转载。

https://www.prolightsfxjh.com/

Thank you!

                                                                                                                                             ------from ProLightsfx