← 返回题目列表

Codeforces · 1665/E

E. 最小化

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

给定一个由 $$$n$$$ 个非负整数组成的数组 $$$a$$$,编号从 $$$1$$$ 到 $$$n$$$。

让我们将数组 $$$a$$$ 的成本定义为 $$$\displaystyle \min_{i \neq j} a_i | a_j$$$,其中$$$|$$$表示按位或运算。

有 $$$q$$$ 查询。对于每个查询,您都会获得两个整数 $$$l$$$ 和 $$$r$$$ ($$$l < r$$$)。对于每个查询,您应该找到子数组 $$$a_{l}, a_{l + 1}, \ldots, a_{r}$$$ 的成本。

输入

每个测试用例由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 10^5$$$) — 长度数组 $$$a$$$。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i < 2^{30}$$$) - $$$a$$$ 的元素。

每个测试用例的第三行包含一个整数 $$$q$$$ ($$$1 \le q \le 10^5$$$) — 查询数。

接下来的 $$$q$$$ 行包含两个整数 $$$l_j$$$、$$$r_j$$$ ($$$1 \le l_j < r_j \le n$$$) — 第 $$$j$$$ 查询的描述。

保证所有测试用例的 $$$n$$$ 总和和 $$$q$$$ 总和不超过 $$$10^5$$$。

输出

对于每个测试用例,打印 $$$q$$$ 数字,其中第 $$$j$$$ 数字是数组 $$$a_{l_j}, a_{l_j + 1}, \ldots, a_{r_j}$$$ 的成本。

示例

输入 #1

2
5
6 1 3 2 1
4
1 2
2 3
2 4
2 5
4
0 2 1 1073741823
4
1 2
2 3
1 3
3 4

输出 #1

7
3
3
1
2
3
1
1073741823

注意

在第一个测试用例中,数组 $$$a$$$ 是

$$$110_2, 001_2, 011_2, 010_2, 001_2$$$.

这就是为什么查询的答案是:

- $$$[1; 2]$$$:$$$a_1 | a_2 = 110_2 | 001_2 = 111_2 = 7$$$;
- $$$[2; 3]$$$:$$$a_2 | a_3 = 001_2 | 011_2 = 011_2 = 3$$$;
- $$$[2; 4]$$$:$$$a_2 | a_3 = a_3 | a_4 = a_2 | a_4 = 011_2 = 3$$$;
- $$$[2; 5]$$$:$$$a_2 | a_5 = 001_2 = 1$$$。

在第二个测试用例中,数组 $$$a$$$ 是

$$$00_2, 10_2, 01_2, \underbrace{11\ldots 1_2}_{30}$$$ ($$$a_4 = 2^{30} - 1$$$)。

这就是为什么查询的答案是:

- $$$[1; 2]$$$:$$$a_1 | a_2 = 10_2 = 2$$$;
- $$$[2; 3]$$$:$$$a_2 | a_3 = 11_2 = 3$$$;
- $$$[1; 3]$$$:$$$a_1 | a_3 = 01_2 = 1$$$;
- $$$[3; 4]$$$:$$$a_3 | a_4 = 01_2 | \underbrace{11\ldots 1_2}_{30} = 2^{30} - 1 = 1073741823$$$。