A16726. Build XOR on a Segment
编程题
提高+/省选-
知识点
题目描述
给定一个长度为 $n$ 的整数数组 $a_1, a_2, \dots, a_n$，其中所有数字均在 $1$ 到 $2^{12} - 1$ 范围内。
你需要处理 $q$ 次询问。每次询问由三个整数 $l_i, r_i, x_i$ 定义：你需要找到一个最小集合 $S = \{s_1, s_2, \dots, s_k\}$，满足以下条件：
- 每个 $s_j$ 等于 $a_{l_i}, a_{l_i + 1}, \dots, a_{r_i}$ 这个子数组中的某个元素；
- $s_1 \oplus s_2 \oplus \dots \oplus s_k = x_i$，其中 $\oplus$ 表示按位异或运算。
你需要处理 $q$ 次询问。每次询问由三个整数 $l_i, r_i, x_i$ 定义：你需要找到一个最小集合 $S = \{s_1, s_2, \dots, s_k\}$，满足以下条件：
- 每个 $s_j$ 等于 $a_{l_i}, a_{l_i + 1}, \dots, a_{r_i}$ 这个子数组中的某个元素；
- $s_1 \oplus s_2 \oplus \dots \oplus s_k = x_i$，其中 $\oplus$ 表示按位异或运算。
输入格式
第一行包含一个整数 $n$（$2 \le n \le 10^4$）。
第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le 2^{12} - 1$）。
第三行包含一个整数 $q$（$1 \le q \le 10^6$）。
接下来 $q$ 行，每行包含三个整数 $l_i, r_i, x_i$（$1 \le l_i \le r_i \le n$，$1 \le x_i \le 2^{12} - 1$）。
第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le 2^{12} - 1$）。
第三行包含一个整数 $q$（$1 \le q \le 10^6$）。
接下来 $q$ 行，每行包含三个整数 $l_i, r_i, x_i$（$1 \le l_i \le r_i \le n$，$1 \le x_i \le 2^{12} - 1$）。
输出格式
对于每个询问，输出一个整数，表示所需集合的最小大小。如果不存在这样的集合，则输出 $0$。
输入输出样例
输入 #1
7 3 5 4 1 7 3 1 5 1 3 1 1 4 1 1 3 2 4 7 5 1 7 8
输出 #1
2 1 3 3 0
说明/提示
考虑示例中的询问：
- 对于第一个询问，可以选择 $S = \{5, 4\}$；
- 对于第二个询问，可以选择 $S = \{1\}$；
- 对于第三个询问，可以选择 $S = \{4, 3, 5\}$；
- 对于第四个询问，可以选择 $S = \{1, 3, 7\}$。
- 对于第一个询问，可以选择 $S = \{5, 4\}$；
- 对于第二个询问，可以选择 $S = \{1\}$；
- 对于第三个询问，可以选择 $S = \{4, 3, 5\}$；
- 对于第四个询问，可以选择 $S = \{1, 3, 7\}$。