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

这是一个比较典型的异或问题，可以使用字典树来解决。具体思路如下：

1. 预处理出数组中任意两个数异或的结果，并将这些结果插入到字典树中。

2. 对于每个数a[i]，在字典树中查找异或结果中第k大的数，即可得到对应的aj的值。

以下是对应的C++代码实现：

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10;

int n, k, tot;
int a[N], trie[N * 30][2], cnt[N * 30];

void insert(int x) {
    int p = 0;
    for (int i = 30; i >= 0; i--) {
        int u = (x >> i) & 1;
        if (!trie[p][u]) trie[p][u] = ++tot;
        p = trie[p][u];
        cnt[p]++;
    }
}

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

int main() {
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        insert(a[i]);
    }
    for (int i = 1; i <= n; i++) {
        printf("%d ", query(a[i]));
    }
    return 0;
}

时间复杂度为O(nlogk)。