← 返回题目列表

Codeforces · 2170/F

F. 在段上构建 XOR

中文机器翻译题面 查看原题

给你一个 $$$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$$$ 等于子数组中从第 $$$l_i$$$ 位置到第 $$$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$$$ 行。其中第 $$$i$$$ 包含三个整数 $$$l_i、r_i、x_i$$$ ($$$1 \le l_i \le r_i \le n$$$; $$$1 \le x_i \le 2^{12} - 1$$$)。

输出

对于每个查询,打印一个整数 — 所需集合的最小大小。如果这样的集合不存在,则打印$$$0$$$。

示例

输入
复制

7
3 5 4 1 7 3 1
5
1 3 1
1 4 1
1 3 2
4 7 5
1 7 8

输出
复制

2 1 3 3 0 

注意

考虑示例中的查询:

  • 在第一个查询中,可以选择$$$S = \{5, 4\}$$$;
  • 在第二个查询中,可以选择$$$S = \{1\}$$$;
  • 在第三个查询中,可以选择$$$S = \{4, 3, 5\}$$$;
  • 在第四个查询中,您可以选择$$$S = \{1, 3, 7\}$$$。