← 返回题目列表

Codeforces · 983/B

B. 异或金字塔

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

对于长度为 $$$m$$$ 的数组 $$$b$$$,我们将函数 $$$f$$$ 定义为

$$$ f(b) = \begin{cases} b[1] & \quad \text{if } 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$$$ 是按位异或。

例如,$$$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$$$ 行 — 查询的答案。

示例

输入 #1

3
8 4 1
2
2 3
1 2

输出 #1

5
12

输入 #2

6
1 2 4 8 16 32
4
1 6
2 5
3 4
1 2

输出 #2

60
30
12
3

注意

在两个查询的第一个示例中,函数的最大值在等于整个段的子段上达到。

在第二个示例中,第一个查询的最佳分段是 $$$[3,6]$$$,第二个查询的最佳分段是 $$$[2,5]$$$,第三个查询的最佳分段是 $$$[3,4]$$$,第四个查询的最佳分段是 $$$[1,2]$$$。