← 返回题目列表

Codeforces · 1100/F

F. 伊万和汉堡

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

Ivan 喜欢汉堡和花钱。 Ivan 住的街上有 $$$n$$$ 汉堡店。 Ivan 有 $$$q$$$ 个朋友,第 $$$i$$$ 个朋友建议在 $$$l_i$$$ 会所见面,然后步行前往 $$$r_i$$$ $$$(l_i \leq r_i)$$$。当与第 $$$i$$$ 个朋友一起散步时,Ivan 可以访问满足 $$$l_i \leq x \leq r_i$$$ 的所有关节 $$$x$$$。

对于每个关节,Ivan 都知道其中最昂贵的汉堡的成本,它的成本为 $$$c_i$$$ burles。伊万想在途中参观一些餐馆,在每个餐馆中他都会买最贵的汉堡并花最多的钱。但有一个小问题:他的卡坏了,不再向他收取购物费用,而是卡上的金额发生了如下变化。

如果 Ivan 在购买之前有 $$$d$$$ burles,并且他在关节处花费了 $$$c$$$ burles,那么在购买之后他将拥有 $$$d \oplus c$$$ burles,其中 $$$\oplus$$$ 表示按位异或运算。

目前 Ivan 有 $$$2^{2^{100}} - 1$$$ burles,他想出去散步。帮助他确定如果他和朋友 $$$i$$$ 一起去散步,他可以花费的最大 burles 数量。他花费的 burles 金额定义为他帐户上的初始金额与最终帐户金额之间的差额。

输入

第一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 500\,000$$$) — 汉堡店的数量。

下一行包含 $$$n$$$ 整数 $$$c_1, c_2, \ldots, c_n$$$ ($$$0 \leq c_i \leq 10^6$$$),其中 $$$c_i$$$ — 汉堡店 $$$i$$$ 中最贵汉堡的成本。

第三行包含一个整数 $$$q$$$ ($$$1 \leq q \leq 500\,000$$$) — Ivan 的朋友数量。

接下来的 $$$q$$$ 行包含两个整数 $$$l_i$$$ 和 $$$r_i$$$ ($$$1 \leq l_i \leq r_i \leq n$$$) — Ivan 将行走的汉堡店数量对。

输出

输出 $$$q$$$ 行,其中 $$$i$$$ 包含 Ivan 可以与朋友 $$$i$$$ 一起花费的最大金额。

示例

输入 #1

4
7 2 3 4
3
1 4
2 3
1 3

输出 #1

7
3
7

输入 #2

5
12 14 23 13 7
15
1 1
1 2
1 3
1 4
1 5
2 2
2 3
2 4
2 5
3 3
3 4
3 5
4 4
4 5
5 5

输出 #2

12
14
27
27
31
14
25
26
30
23
26
29
13
13
7

注意

在第一个测试中,为了与第一个和第三个朋友花最多的钱,Ivan 只需要进入第一个汉堡即可。伊万和第二个朋友一起去了第三个汉堡。

在对第三个朋友(要从第一个汉堡走到第三个汉堡)的第二次测试中,只有 8 个花钱选项 - $$$0$$$、$$$12$$$、$$$14$$$、$$$23$$$、$$$12 \oplus 14 = 2$$$、$$$14 \oplus 23 = 25$$$、 $$$12 \oplus 23 = 27$$$,$$$12 \oplus 14 \oplus 23 = 20$$$。如果您去第一个和第三个汉堡,则结果花费的最大金额为 $$$12 \oplus 23 = 27$$$。