Bài này yêu sử dụng kiến thức về Trie. Mỗi số có thể coi như một xâu nhị phân ~31~ bit (vì ~10^{9}~ < ~2^{31})~. Sau khi chèn các xâu nhị phân vào cây Trie, với mỗi node của cây ta tính thêm trường size là số lá trong gốc cây con. Dựa vào trường size này ta dễ dàng thực hiện truy vấn tìm số hạng thứ ~K~, việc này có thể thực hiện tương tự như việc tìm kiếm một node trên cây BST, ta sẽ đi từ gốc xuống lá, tại mỗi node thì nếu ~k \leq~ size(cây con trái) thì ta nhảy sang trái, nếu không thì nhảy sang phải và cộng kết quả thêm một lượng lũy thừa ~2~ tương ứng với độ sâu của node hiện tại.

Để xử lí truy vấn xor tất cả các số, ta chỉ việc quản lí thêm một mảng flipped[] ở mỗi độ cao. Phép xor với ~X~ chỉ đơn giản là thay đổi trạng thái của flipped[] ở những vị trí bit ~1~ của ~X~.

Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này

Code mẫu của ladpro98

#include <bits/stdc++.h>

using namespace std;

const int LENGTH = 30;

struct Node {
    Node *son[2];
    int size;
    Node() { son[0] = son[1] = NULL; size = 0; }
};

int size(Node *x) { return x ? x->size : 0; }

Node *root;
bool flip[LENGTH + 1];

void insertBinary(Node *x, int v, int pos) {
    int bit = v >> pos & 1;
    if (!x->son[bit]) x->son[bit] = new Node();
    if (pos > 0)
        insertBinary(x->son[bit], v, pos - 1);
    else
        ++x->son[bit]->size;
    x->size = size(x->son[0]) + size(x->son[1]);
}

void xorWith(int v) {
    for (int i = LENGTH; i >= 0; --i) if (v >> i & 1)
        flip[i] ^= 1;
}

int findKth(Node *x, int kth, int pos) {
    if (pos < 0) return 0;
    int smaller = size(x->son[flip[pos]]);
    if (kth <= smaller) return findKth(x->son[flip[pos]], kth, pos - 1);
    return findKth(x->son[!flip[pos]], kth - smaller, pos - 1) + (1 << pos);
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n, nQuery; cin >> n >> nQuery;
    root = new Node();
    for (int i = 1; i <= n; ++i) {
        int x; cin >> x;
        insertBinary(root, x, LENGTH);
    }
    while (nQuery--) {
        char cmd[5]; int x;
        cin >> cmd >> x;
        if (cmd[0] == 'X')
            xorWith(x);
        else
            cout << findKth(root, n - x + 1, LENGTH) << '\n';
    }
    return 0;
}