[AdditionalFile5217.zip](file://AdditionalFile5217.zip?type=additional_file)

#5217. 「UOI 2024 Stage 4 Day2」将子段归零

标签: 传统 | 时间限制: 6000 ms | 内存限制: 512 MiB |

注意事项

在 LibreOJ 上，由于语言限制，目前只支持以下语言的提交：

• C++（标准为 C++ 17 及以上）

请在提交源代码前添加 #include "grader.h"。

题目描述

题目译自 Ukrainian Olympiads in Informatics 2024 Stage 4 Day2 T4. Занулити пiдвiдрiзок

这是一个交互题。

对于一个长度为 $m$ 的正整数数组 $b$，我们定义 $f(b)$ 如下：

• 初始时，某个变量 $x$ 等于 $0$；
• 花费一枚硬币可以将 $x$ 的值增加 $1$；
• 花费一枚硬币可以选择数组中的一个元素 $b_i$ $(1 \le i \le m)$，并将其替换为 $(b_i \oplus x)$，其中 $\oplus$ 表示按位异或操作；
• $f(b)$ 等于使数组 $b$ 的所有元素同时变为 $0$ 所需的最小硬币数量。

按位异或操作对于非负整数 $a$ 和 $b$ 的结果 $(a \oplus b)$ 是一个非负整数，其二进制表示中某一位为 $1$，当且仅当 $a$ 和 $b$ 的二进制表示在该位上的值不同。例如，$3_{10} \oplus 5_{10} = 0011_{2} \oplus 0101_{2} = 0110_{2} = 6_{10}$。

给定一个长度为 $n$ 的正整数数组 $a$ 和 $q$ 个查询，每个查询形式为 $l, r$。对于每个查询，你需要计算 $f([a_l, a_{l+1}, \ldots, a_r])$。

交互方式

你需要实现以下函数：

void init(integer n, array of integers a)

• $n$：一个整数，表示数组的长度；
• $a$：一个长度为 $n$ 的整数数组；
• 该函数不返回任何值。

integer ask(integer l, integer r)

• $l$：一个整数，表示查询的左边界；
• $r$：一个整数，表示查询的右边界；
• 该函数返回一个整数，即 $f([a_l, a_{l+1}, \ldots, a_r])$。

array of integers askAll(integer q, array of integers l, array of integers r)

• $q$：一个整数，表示查询的数量；
• $l$：一个长度为 $q$ 的整数数组，$l_i$ 表示第 $i$ 个查询的左边界；
• $r$：一个长度为 $q$ 的整数数组，$r_i$ 表示第 $i$ 个查询的右边界；
• 该函数返回一个整数数组，其中第 $i$ 个数等于第 $i$ 个查询的答案。

输入格式

输入的第一行包含三个整数 $n, q, t$ $(1 \leq n, q \leq 2 \cdot 10^5, 1 \leq t \leq 2)$，分别表示数组元素的数量、查询的数量和查询的格式。

第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$ $(1 \leq a_i < 2^{60})$，表示数组 $a$ 的元素。

接下来的 $q$ 行，每行包含两个整数 $l$ 和 $r$ $(1 \leq l \leq r \leq n)$，表示第 $i$ 个查询的参数。

程序开始时，init 函数将被调用一次。

如果 $t=1$，askAll 函数将被调用一次，包含所有查询。如果 $t=2$，ask 函数将被调用 $q$ 次。

输出格式

交互器将为每个查询单独输出一行一个整数，表示查询的答案。

样例 1

输入

7 6 1
5 4 3 5 7 7 7
1 4
4 7
3 7
1 7
2 6
1 1

输出

9
11
12
14
12
6

样例 2

输入

7 6 2
5 4 3 5 7 7 7
1 4
4 7
3 7
1 7
2 6
1 1

输出

9
11
12
14
12
6

数据范围与提示

详细子任务附加限制及分值如下表所示：