题解思路

关键观察

初始矩阵全为 0。对第 i 行异或一次得到该行所有元素都异或上 x_i；对第 j 列异或一次得到该列所有元素都异或上 y_j。 同一行/列多次操作只看奇偶次（偶数次等于没操作）。设：

• r_i ∈ {0,1} 表示第 i 行是否被操作（奇数次为 1）；
• c_j ∈ {0,1} 表示第 j 列是否被操作（奇数次为 1）。

则任意位置

$$a_{i,j} = (r_i ? x_i : 0)\ \oplus\ (c_j ? y_j : 0) $$

特别地，在主对角线上：

$$z_i = a_{i,i} = (r_i ? x_i : 0)\ \oplus\ (c_i ? y_i : 0) $$

因为题目保证 x_i, y_i 均为正且互不相同，集合 $\{0,\ x_i,\ y_i,\ x_i \oplus y_i\}$ 四个值两两不同。 因此，给定 z_i 可以唯一确定 (r_i, c_i)：

• z_i = 0 → (r_i,c_i) = (0,0)
• z_i = x_i → (r_i,c_i) = (1,0)
• z_i = y_i → (r_i,c_i) = (0,1)
• z_i = x_i^y_i→ (r_i,c_i) = (1,1)

一旦得到了所有 r_i, c_i，就能预处理：

• R_i = (r_i ? x_i : 0)
• C_j = (c_j ? y_j : 0)

回答查询 (u,v) 时，直接输出 R_u ^ C_v 即可。

复杂度分析

• 预处理：O(n)
• 每次查询：O(1)
• 总复杂度：O(n + q)，空间 O(n)。

代码

Python

import sys

def main():
    data = list(map(int, sys.stdin.read().strip().split()))
    it = iter(data)
    n = next(it); q = next(it)
    x = [0]*(n+1)
    y = [0]*(n+1)
    z = [0]*(n+1)
    for i in range(1, n+1):
        x[i] = next(it)
    for i in range(1, n+1):
        y[i] = next(it)
    for i in range(1, n+1):
        z[i] = next(it)

    R = [0]*(n+1)
    C = [0]*(n+1)
    for i in range(1, n+1):
        xi, yi, zi = x[i], y[i], z[i]
        # 依据四种唯一情况确定 r_i, c_i
        if zi == 0:
            R[i] = 0
            C[i] = 0
        elif zi == xi:
            R[i] = xi
            C[i] = 0
        elif zi == yi:
            R[i] = 0
            C[i] = yi
        else:
            # 必为 xi ^ yi
            R[i] = xi
            C[i] = yi

    out = []
    for _ in range(q):
        u = next(it); v = next(it)
        out.append(str(R[u] ^ C[v]))
    sys.stdout.write("\n".join(out))

if __name__ == "__main__":
    main()

Java

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        // 读完整输入到 tokens，提高速度
        StringBuilder sbAll = new StringBuilder();
        String line;
        while ((line = br.readLine()) != null) sbAll.append(line).append(' ');
        StringTokenizer st = new StringTokenizer(sbAll.toString());

        int n = Integer.parseInt(st.nextToken());
        int q = Integer.parseInt(st.nextToken());

        int[] x = new int[n + 1];
        int[] y = new int[n + 1];
        int[] z = new int[n + 1];
        for (int i = 1; i <= n; i++) x[i] = Integer.parseInt(st.nextToken());
        for (int i = 1; i <= n; i++) y[i] = Integer.parseInt(st.nextToken());
        for (int i = 1; i <= n; i++) z[i] = Integer.parseInt(st.nextToken());

        int[] R = new int[n + 1];
        int[] C = new int[n + 1];

        for (int i = 1; i <= n; i++) {
            int xi = x[i], yi = y[i], zi = z[i];
            if (zi == 0) {
                R[i] = 0; C[i] = 0;
            } else if (zi == xi) {
                R[i] = xi; C[i] = 0;
            } else if (zi == yi) {
                R[i] = 0; C[i] = yi;
            } else { // 必为 xi ^ yi
                R[i] = xi; C[i] = yi;
            }
        }

        StringBuilder out = new StringBuilder();
        for (int k = 0; k < q; k++) {
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            out.append(R[u] ^ C[v]).append('\n');
        }
        System.out.print(out.toString());
    }
}

C++

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, q;
    if (!(cin >> n >> q)) return 0;
    vector<int> x(n+1), y(n+1), z(n+1);
    for (int i = 1; i <= n; ++i) cin >> x[i];
    for (int i = 1; i <= n; ++i) cin >> y[i];
    for (int i = 1; i <= n; ++i) cin >> z[i];

    vector<int> R(n+1), C(n+1);
    for (int i = 1; i <= n; ++i) {
        int xi = x[i], yi = y[i], zi = z[i];
        if (zi == 0) {
            R[i] = 0; C[i] = 0;
        } else if (zi == xi) {
            R[i] = xi; C[i] = 0;
        } else if (zi == yi) {
            R[i] = 0; C[i] = yi;
        } else { // 必为 xi ^ yi
            R[i] = xi; C[i] = yi;
        }
    }

    while (q--) {
        int u, v; cin >> u >> v;
        cout << (R[u] ^ C[v]) << '\n';
    }
    return 0;
}

题目内容

小杰有一个 $n×n$ 的矩阵，和两个由 $n$ 个互不相同的整数组成的数组 {$x_1,x_2,...,x_n$} 和 {$y_1,y_2,...,y_n$} 。

为了方便描述，我们使用 $a_{ij}$ 表示矩阵的第 $i$ 行第 $j$ 列的元素。起初，矩阵中每个元素都等于 $0$ ，直到他对矩阵进行了若干次以下两种操作(次数未知)：

• 操作一：选择第 $i$ 行，将该行所有元素与 $x_i$ 进行按位异或(xor)操作；

• 操作二：选择第 $j$ 列，将该列所有元素与 $y_j$ 进行按位异或(xor)操作。

现在已知主对角线从左上角到右下角第 $i$ 个位置的最终值为 $z_i$ ，需要回答 $q$ 次询问，每次你需要求出 $a_{u,v}$ 的元素值。

【名词解释】

矩阵的主对角线为从左上角到右下角的直线，即所有满足 $i=j$ 的元素 $a_{ij}$ 组成的集合。

输入描述

第一行输入两个整数 $n$ 和 $q(1 ≦ n,q≦ 10^5)$ ，分别表示矩阵的维度和询问次数；

第二行输入 $n$ 个互不相同的整数 $x_1,x_2,….,x_n(1≦x_i≦ 10^6)$ 代表行异或值；

第三行输入 $n$ 个互不相同的整数 $y_1,y_2,….,y_n(1≦y_i≦ 10^6)$ 代表行异或值；

第四行输入 $n$ 个整数 $z_1,z_2,….,z_n(0≦z_i≦ 10^6)$ ，表示主对角线的最终值；

此后 $q$ 行，每行输入两个整数 $u$ 和 $v(1 ≦u,v≦ n)$ ，表示询问的位置。

除此之外，保证 $x_i$ 和 $y_i$ 的值互不相同。

输出描述

对于每次询问，新起一行。输出一个整数，表示询问的元素值。保证输入的 $z_i$ 值与至少一种有效的操作序列对应。

如果存在多个解决方案，您可以输出任意一个，系统会自动判定是否正确。注意，自测运行功能可能因此返回错误结果，请自行检查答案正确性。

样例1

输入

2 1
1 2
3 4
1 4
1 2

输出

5

说明

在这个样例中，矩阵的其中一种合法的变化过程为：

样例2

输入

3 2
1 2 4
8 16 32
1 16 36
1 3
2 3

输出

33
32