practice/trie_bit.cpp at master · Autoratch/practice · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include <bits/stdc++.h>
using namespace std;

const int N = 1 << 18;
const int K = 30;

int t,n,k,cnt;
int tree[N][2],val[N];

void update(int x)
{
    int now = 0;
    for(int i = K;i >= 0;i--)
    {
        int y = x&(1 << i);
        if(y) y = 1;
        if(tree[now][y]) now = tree[now][y];
        else tree[now][y] = ++cnt,now = tree[now][y];
    }
    val[now] = x;
}

int query(int x)
{
    int now = 0;
    for(int i = K;i >= 0;i--)
    {
        int y = x&(1 << i);
        if(y) y = 0; else y = 1;
        if(tree[now][y]) now = tree[now][y];
        else now = tree[now][y^1];
    }
    return val[now];
}

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);

    cin >> t;
    while(t--)
    {
        cin >> n >> k;
        int s = 0,mx = 0,ans;
        cnt = 0;
        for(int i = 0;i < N;i++) tree[i][0] = tree[i][1] = val[i] = 0;
        update(0);
        for(int i = 0;i < n;i++)
        {
            int x;
            cin >> x;
            s^=x;
            int ret = query(s^k);
            if((ret^s^k)>mx) mx = ret^s^k,ans = ret^s;
            update(s);
        }
        cout << ans << '\n';
    }
}