Binary Trie

$0$ 以上 $2^B$ 未満の整数を $B$ 桁の 2 進数で表し、上の桁から順に Trie の辺としてたどって入れます。同じ値を何個でも入れられ（多重集合）、すべての要素をまとめて xor することもできます。以下、入っている要素を $a$ とします。

• BinaryTrie(B): 空の集合で初期化（既定は $B = 30$。値が $10^{18}$ 程度までなら $B = 60$）
• add(x, k): $x$ を $k$ 個加える（既定は $k = 1$）
• discard(x, k): $x$ を $k$ 個取り除き、取り除いた個数を返す（既定は $k = 1$。入っている個数が少なければすべて取り除く）
• count(x): $x$ の個数
• xor_all(x): すべての要素 $a$ を $a \oplus x$ に変える。 $O(1)$
• kth(k, y): $a \oplus y$ を小さい順に並べたときの $k$ 番目（0-indexed）の値（既定は $y = 0$ で、 $k$ 番目に小さい要素）
• min_xor(y), max_xor(y): $a \oplus y$ の最小値・最大値（空でないときだけ使う）
• count_less(x, y): $a \oplus y < x$ となる要素の個数（既定は $y = 0$ で、 $x$ 未満の要素の個数）
• len(t): 要素の個数
• 計算量: xor_all と len 以外は $O(B)$

kth などは $a \oplus y$ の値を返すので、要素 $a$ そのものが欲しいときは、返り値と $y$ の xor を取ります。ノードは取り除いても消さないので、メモリは加えた値の種類数 $\times B$ に比例します。

例（列から 2 つ選んだときの xor の最大値）:

t = BinaryTrie(30)
ans = 0
for x in a:
    if len(t):
        ans = max(ans, t.max_xor(x))
    t.add(x)

コード

class BinaryTrie:
    # 0 以上 2^bit 未満の整数の多重集合
    def __init__(self, bit=30):
        self.bit = bit
        self.ch = [-1, -1]  # ch[2v + b] = ノード v の、次のビットが b の子（なければ -1）
        self.cnt = [0]      # cnt[v] = ノード v の下にある要素の個数
        self.lazy = 0       # 全要素に xor する値

    def __len__(self):
        return self.cnt[0]

    def xor_all(self, x):
        # すべての要素を (要素) xor x に変える
        self.lazy ^= x

    def add(self, x, k=1):
        # x を k 個加える
        x ^= self.lazy
        v = 0
        self.cnt[0] += k
        for i in range(self.bit - 1, -1, -1):
            j = 2 * v + (x >> i & 1)
            if self.ch[j] == -1:
                self.ch[j] = len(self.cnt)
                self.ch.append(-1)
                self.ch.append(-1)
                self.cnt.append(0)
            v = self.ch[j]
            self.cnt[v] += k

    def count(self, x):
        x ^= self.lazy
        v = 0
        for i in range(self.bit - 1, -1, -1):
            v = self.ch[2 * v + (x >> i & 1)]
            if v == -1:
                return 0
        return self.cnt[v]

    def discard(self, x, k=1):
        # x を k 個（入っている個数が少なければすべて）取り除き、取り除いた個数を返す
        k = min(k, self.count(x))
        if k == 0:
            return 0
        x ^= self.lazy
        v = 0
        self.cnt[0] -= k
        for i in range(self.bit - 1, -1, -1):
            v = self.ch[2 * v + (x >> i & 1)]
            self.cnt[v] -= k
        return k

    def kth(self, k, y=0):
        # (要素) xor y を小さい順に並べたときの k 番目（0-indexed）の値
        m = self.lazy ^ y
        v = 0
        res = 0
        for i in range(self.bit - 1, -1, -1):
            b = m >> i & 1
            c = self.ch[2 * v + b]
            if c != -1 and self.cnt[c] > k:
                v = c
            else:
                if c != -1:
                    k -= self.cnt[c]
                v = self.ch[2 * v + (b ^ 1)]
                res |= 1 << i
        return res

    def min_xor(self, y=0):
        # (要素) xor y の最小値
        return self.kth(0, y)

    def max_xor(self, y=0):
        # (要素) xor y の最大値
        return self.kth(self.cnt[0] - 1, y)

    def count_less(self, x, y=0):
        # (要素) xor y が x 未満の要素の個数
        if x <= 0:
            return 0
        if x >> self.bit:
            return self.cnt[0]
        m = self.lazy ^ y
        v = 0
        res = 0
        for i in range(self.bit - 1, -1, -1):
            b = m >> i & 1
            if x >> i & 1:
                c = self.ch[2 * v + b]
                if c != -1:
                    res += self.cnt[c]
                b ^= 1
            v = self.ch[2 * v + b]
            if v == -1:
                break
        return res