CF983B XOR-pyramid

对于长度为 $m$ 的数组 $b$，我们定义函数 $f$ 如下： $$ f(b) = \begin{cases} b[1] & \quad \text{如果 } m = 1 \\ f(b[1] \oplus b[2],\, b[2] \oplus b[3],\, \dots,\, b[m-1] \oplus b[m]) & \quad \text{否则} \end{cases} $$ 其中 $\oplus$ 表示[按位异或](https://en.wikipedia.org/wiki/Bitwise_operation#XOR)。 例如，$f(1,2,4,8)=f(1\oplus2,2\oplus4,4\oplus8)=f(3,6,12)=f(3\oplus6,6\oplus12)=f(5,10)=f(5\oplus10)=f(15)=15$。 现在给定一个数组 $a$ 和若干个询问。每个询问由两个整数 $l$ 和 $r$ 表示。对于每个询问，答案是 $a_l, a_{l+1}, \ldots, a_r$ 的所有连续子段中 $f$ 的最大值。

第一行包含一个整数 $n$（$1 \le n \le 5000$），表示数组 $a$ 的长度。 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$0 \le a_i \le 2^{30}-1$），表示数组的元素。 第三行包含一个整数 $q$（$1 \le q \le 100\,000$），表示询问的数量。 接下来的 $q$ 行，每行包含两个整数 $l$ 和 $r$（$1 \le l \le r \le n$），表示一次询问。

输出 $q$ 行，每行一个答案，表示对应询问的结果。

在第一个样例中，两次询问的最大值都出现在整个区间上。 在第二个样例中，第一次询问的最优区间是 $[3,6]$，第二次询问是 $[2,5]$，第三次询问是 $[3,4]$，第四次询问是 $[1,2]$。 由 ChatGPT 4.1 翻译