P12559 [UOI 2024] Zeroing the segment

**本题采用交互式评测方式，目前仅支持 C++ 语言提交。** 对于一个长度为 $m$ 的正整数数组 $b$，我们定义 $f(b)$ 如下： - 初始时设变量 $x$ 为 $0$； - 每次可以花费 **1 枚硬币** 将 $x$ 的值增加 $1$； - 每次可以花费 **1 枚硬币** 选择数组中的元素 $b_i$（$1\le i\le m$）并将其替换为 $(b_i \oplus x)$，其中 $\oplus$ 表示 **按位异或** 运算； - $f(b)$ 表示将所有数组元素同时变为 $0$ 所需的最少硬币数。 **按位异或** 运算（$\oplus$）的定义：对于非负整数 $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$ 个查询的答案。 这三个函数在 C++ 语言中可以视作： ```cpp void init(int n, const vector &a); long long ask(int l, int r); vector askAll(int q, const vector &l, const vector &r); ```

第一行包含三个整数 $n$、$q$ 和 $t$（$1 \leq n, q \leq 2 \cdot 10^5$；$1 \leq t \leq 2$）—— 分别表示数字数量、查询数量和查询格式。 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \leq a_i < 2^{60}$）—— 数组 $a$ 的元素。 接下来 $q$ 行每行包含两个整数 $l$ 和 $r$（$1 \leq l \leq r \leq n$）—— 第 $i$ 个查询的参数。 函数 $\tt{init}$ 将被调用恰好一次。 如果 $t=1$，则函数 $\tt{askAll}$ 将被调用恰好一次来处理所有查询。如果 $t=2$，则函数 $\tt{ask}$ 将被调用恰好 $q$ 次。

评测程序将输出 $q$ 个整数，每个查询的答案各占一行。

### 评分标准 - （$3$ 分）：$t=1$，且对所有 $1\le i\le n$ 有 $a_i=a_1$； - （$8$ 分）：$t=1$，且对所有 $i \neq j$ 有 $a_i \neq a_j$； - （$3$ 分）：$t=1$，且存在自然数 $m$ 使得对所有 $i$ 有 $2^m+n \le a_i