思路与算法

对Y的每个前缀建立31层持久化二进制Trie，节点保存子树元素个数。一次询问为每个X[u..d]维护Y[l..r]的两个版本游标。从最高位向下，先统计所有游标中使异或当前位为1的元素总数；若不少于k则答案置1并进入相反位，否则扣去该数量并进入同位。每位同时更新全部游标。

正确性说明

版本差精确给出当前Y区间里某个二进制前缀的出现次数，重复数也逐个计数。高位不同的异或值大小已确定，故把全部候选按本位1/0分组，按秩选择整组不会排除第k大。逐位归纳，最终得到所求值。

复杂度

建Trie初始化和复制O(31M)，空间O(31M+N)。每次询问游标初始化O(d-u+1)，31轮各扫描该长度，总O(31(d-u+1))；总时间O(31M+31PN)，计数使用64位。

易错点

输入元素小于2^31，只读位30到0。k是第k大而非第k小；必须保留重数。最多3亿矩阵位置，不能实际构造矩阵。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
struct Node {
    int a[2], cnt;
    Node() {
        a[0] = a[1] = cnt = 0;
    }
};
int main() {
    int n, m;
    cin >> n >> m;
    vector<int> x(n), y(m), root(m + 1);
    for (int &v : x)
        cin >> v;
    for (int &v : y)
        cin >> v;
    vector<Node> tr(1);
    tr.reserve((size_t)m * 32 + 1);
    for (int i = 1; i <= m; i++) {
        root[i] = tr.size();
        tr.push_back(tr[root[i - 1]]);
        int u = root[i], v = root[i - 1];
        tr[u].cnt++;
        for (int b = 30; b >= 0; b--) {
            int z = (y[i - 1] >> b) & 1;
            tr[u].a[z] = tr.size();
            tr.push_back(tr[tr[v].a[z]]);
            u = tr[u].a[z];
            v = tr[v].a[z];
            tr[u].cnt++;
        }
    }
    int q;
    cin >> q;
    while (q--) {
        int u, d, l, r;
        long long k;
        cin >> u >> d >> l >> r >> k;
        vector<int> a(d - u + 1, root[r]), b(d - u + 1, root[l - 1]);
        int ans = 0;
        for (int bit = 30; bit >= 0; bit--) {
            long long c = 0;
            for (int i = u - 1; i < d; i++) {
                int z = ((x[i] >> bit) & 1) ^ 1, j = i - u + 1;
                c += tr[tr[a[j]].a[z]].cnt - tr[tr[b[j]].a[z]].cnt;
            }
            int want = c >= k;
            if (want)
                ans |= 1 << bit;
            else
                k -= c;
            for (int i = u - 1; i < d; i++) {
                int z = ((x[i] >> bit) & 1) ^ want, j = i - u + 1;
                a[j] = tr[a[j]].a[z];
                b[j] = tr[b[j]].a[z];
            }
        }
        cout << ans << '\n';
    }
}