c++代码 给定一个长度为n(n<=1e5)的序列a和一个整数k(k<=1e5)，请对于每个1<=i<=n，求出对应的1<=j<=n，使得ai异或aj第k大。 你需要输出这aj 的值。样例输入 #1 6 2 1 1 4 5 1 4 样例输出 #1 5 5 5 4 5 5

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

const int N = 1e5 + 10, M = 20 * N;
int n, k, idx, trie[M][2], val[M];
int a[N], s[N], tot;

void insert(int x) {
    int u = 0;
    for (int i = 20; i >= 0; i--) {
        int t = x >> i & 1;
        if (!trie[u][t]) trie[u][t] = ++idx;
        u = trie[u][t];
        val[u]++;
    }
}

int query(int x) {
    int u = 0, res = 0;
    for (int i = 20; i >= 0; i--) {
        int t = x >> i & 1;
        if (k > val[trie[u][t ^ 1]]) {
            k -= val[trie[u][t ^ 1]];
            u = trie[u][t];
            res |= 1 << i;
        } else {
            u = trie[u][t ^ 1];
        }
    }
    return res;
}

int main() {
    cin >> n >> k;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = n; i >= 1; i--) s[i] = s[i + 1] ^ a[i];
    for (int i = 1; i <= n; i++) {
        insert(s[i]);
        cout << query(s[i]) << " ";
    }
    cout << endl;
    return 0;
}