2200左右的DS题单

#include <bits/stdc++.h> 
using namespace std;
#define endl "\n" 
typedef long long ll;

const int N = 1e6 + 100;
int Trie[N * 32][2], cnt, n, k;
int num[N * 32];
ll ans;

void insert(int x) {
    int now = 0;
    for (int i = 30; i >= 0; i--) {
        int j = x >> i & 1;
        if (!Trie[now][j]) Trie[now][j] = ++cnt;
        now = Trie[now][j];
        num[now]++;
    }
}

void query(int x) {
    int now = 0;
    for (int i = 30; i >= 0; i--) {
        int j = x >> i & 1;
        if (k >> i & 1) {
            if(!Trie[now][!j]) return;
            now = Trie[now][!j];
        } else {
            ans += num[Trie[now][!j]];
            if(!Trie[now][j]) return;
            now = Trie[now][j];
        }
    }
    ans += num[now];
}

void solve() {
    cin >> n >> k;
    ll now = 0;
    insert(0);
    for(int i = 1; i <= n; i++) {
        int x; cin >> x;
        now ^= x;
        insert(now);
        query(now);
    }
    cout << ans << endl;
}

signed main() {
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);

    // int T = 1; cin >> T;
    // while (T--) solve();
    solve();

    return 0;
}