Codeforces Round #367 (Div. 2) D. Vasiliy's Multiset

問題

Problem - D - Codeforces
3つのクエリに答える．
1. xをmultiset Aに加える
2. xをmultiset Aから取り除く
3. を出力する

解法1

c++のmultisetを使って二分探索をする．
xorをとった値が大きくなるように上位のbitから0か1か決めていけばいい．xを反転したものがAに含まれていればいいのだが，あるとは限らないので上位のbitからそのbitが1(または0)である値が存在するかどうかをlower_boundを使って調べる．見つかればその後はそのbitはその値に固定して探索を行う．見つからなければ，そのbitは妥協して次のbitに移る．計算量は.
実装しているときに<algorithm>で定義されているlower_boundをsetで使うとO(N)かかってしまうことを知った．

解法2

考え方は解法1と同じなのだがトライ木を使ってに抑える．トライ木のノードには1文字格納されており，根から葉までたどることで文字列を高速に検索できる．整数も01の文字列とみなせるのでトライ木を使うことができる．さらに今回は上位bitから探索を行いため非常に相性がいい．あるbitが1(または0)の値が含まれているかはその方向に枝が存在するか確認するだけなので先ほどの解法よりも計算量を抑えられる．

ソースコード1

#include <iostream>
#include <set>
using namespace std;

#define GET_ARG(a,b,c,F,...) F
#define REP3(i,s,e) for (i = s; i <= e; i++)
#define REP2(i,n) REP3 (i,0,(int)(n)-1)
#define REP(...) GET_ARG (__VA_ARGS__,REP3,REP2) (__VA_ARGS__)
#define RREP3(i,s,e) for (i = s; i >= e; i--)
#define RREP2(i,n) RREP3 (i,(int)(n)-1,0)
#define RREP(...) GET_ARG (__VA_ARGS__,RREP3,RREP2) (__VA_ARGS__)

int main(void) {
    int q;
    scanf("%d",&q);
    multiset<unsigned int> st {0};
    while (q--) {
        char op;
        int x;
        scanf("\n%c %d",&op,&x);
        if (op == '+') st.insert(x);
        else if (op == '-') st.erase(st.find(x));
        else {
            int i;
            unsigned int l = 0, r = 1U<<31;
            RREP (i,30,0) {
                if (x & 1<<i) {
                    auto p = st.lower_bound(l);
                    if (*p < (l|1<<i))
                        r = l | 1 << i;
                    else
                        l = l | 1 << i;
                }
                else {
                    auto p = st.lower_bound(l|1<<i);
                    if (p != st.end() && *p < r)
                        l = l | 1 << i;
                    else
                        r = l | 1 << i;
                }
            }
            printf("%d\n",x^l);
        }
    }
    return 0;
}

ソースコード2

#include <iostream>
#include <set>
using namespace std;

#define GET_ARG(a,b,c,F,...) F
#define REP3(i,s,e) for (i = s; i <= e; i++)
#define REP2(i,n) REP3 (i,0,(int)(n)-1)
#define REP(...) GET_ARG (__VA_ARGS__,REP3,REP2) (__VA_ARGS__)
#define RREP3(i,s,e) for (i = s; i >= e; i--)
#define RREP2(i,n) RREP3 (i,(int)(n)-1,0)
#define RREP(...) GET_ARG (__VA_ARGS__,RREP3,RREP2) (__VA_ARGS__)

struct Trie {
    int num;
    struct Trie* parent;
    struct Trie* child[2];
};

struct Trie root;

void add(int val) {
    int i;
    struct Trie* node = &root;
    RREP (i,31) {
        int next = val>>i&1;
        if (node->child[next] == NULL) {
            node->child[next] = new Trie();
            node->child[next]->parent = node;
        }
        node = node->child[next];
    }
    node->num++;
}

void remove(int val) {
    int i;
    struct Trie* node = &root;
    RREP (i,31) {
        node = node->child[val>>i&1];
    }
    if (--node->num) return;
    bool end = false;
    while (node != &root && !end) {
        struct Trie* p = node->parent;
        REP (i,2) {
            if (p->child[i] == NULL || p->child[i] == node) p->child[i] = NULL;
            else end = true;
        }
        delete(node);
        node = p;
    }
}

int query(int val) {
    int i, ret = 0;
    struct Trie* node = &root;
    RREP (i,31) {
        int next = 1 - (val>>i&1);
        if (node->child[next] != NULL) {
            node = node->child[next];
            ret = ret * 2 + next;
        }
        else {
            node = node->child[1-next];
            ret = ret * 2 + 1 - next;
        }
    }
    return ret;
}

int main(void) {
    int q;
    scanf("%d\n",&q);
    add(0);
    while (q--) {
        char op;
        int x;
        scanf("%c %d\n",&op,&x);
        if (op == '+') add(x);
        else if (op == '-') remove(x);
        else printf("%d\n",x^query(x));
    }
    return 0;
}