← 返回题目列表

Codeforces · 1732/C2

C2. 谢赫(硬版)

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

这是问题的困难版本。唯一的区别是在这个版本中 $$$q = n$$$。

给定一个整数数组 $$$a_1, a_2, \ldots, a_n$$$。

数组 $$$[l, r]$$$ 的子段的成本,$$$1 \leq l \leq r \leq n$$$ 的值为 $$$f(l, r) = \operatorname{sum}(l, r) - \operatorname{xor}(l, r)$$$,其中 $$$\operatorname{sum}(l, r) = a_l + a_{l+1} + \ldots + a_r$$$ 和 $$$\operatorname{xor}(l, r) = a_l \oplus a_{l+1} \oplus \ldots \oplus a_r$$$ ($$$\oplus$$$ 代表按位异或)。

您将有 $$$q$$$ 查询。每个查询由一对数字 $$$L_i$$$、$$$R_i$$$ 给出,其中 $$$1 \leq L_i \leq R_i \leq n$$$。您需要找到子段 $$$[l, r]$$$, $$$L_i \leq l \leq r \leq R_i$$$,其最大值为 $$$f(l, r)$$$。如果有多个答案,那么你需要在其中找到一个长度最小的子段,即$$$r - l + 1$$$的最小值。

输入

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

每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$q$$$ ($$$1 \leq n \leq 10^5$$$, $$$q = n$$$) — 数组的长度和查询的数量。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \leq a_i \leq 10^9$$$) — 数组元素。

每个测试用例接下来的 $$$q$$$ 行中的 $$$i$$$ 包含两个整数 $$$L_i$$$ 和 $$$R_i$$$ ($$$1 \leq L_i \leq R_i \leq n$$$) — 我们需要在其中找到段的边界。

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

保证 $$$L_1 = 1$$$ 且 $$$R_1 = n$$$。

输出

对于每个测试用例,打印 $$$q$$$ 数字对 $$$L_i \leq l \leq r \leq R_i$$$,使得值 $$$f(l, r)$$$ 最大,并且其中长度 $$$r - l + 1$$$ 最小。如果有多个正确答案,请打印其中任何一个。

示例

输入 #1

6
1 1
0
1 1
2 2
5 10
1 2
2 2
3 3
0 2 4
1 3
1 2
2 3
4 4
0 12 8 3
1 4
1 3
2 4
2 3
5 5
21 32 32 32 10
1 5
1 4
1 3
2 5
3 5
7 7
0 1 0 1 0 1 0
1 7
3 6
2 5
1 4
4 7
2 6
2 7

输出 #1

1 1
1 1
2 2
1 1
1 1
2 2
2 3
2 3
2 3
2 3
2 3
2 3
2 3
2 3
3 4
2 4
4 6
2 4
2 4
4 6
2 4
2 4

注意

在所有测试用例中,都会考虑第一个查询。

在第一个测试用例中,$$$f(1, 1) = 0 - 0 = 0$$$。

在第二个测试用例中,$$$f(1, 1) = 5 - 5 = 0$$$,$$$f(2, 2) = 10 - 10 = 0$$$。注意 $$$f(1, 2) = (10 + 5) - (10 \oplus 5) = 0$$$,但是我们需要在 $$$f(l, r)$$$ 的最大值中找到长度最小的子段。因此,只有 $$$[1, 1]$$$ 和 $$$[2, 2]$$$ 段才是正确答案。

在第四个测试用例中,$$$f(2, 3) = (12 + 8) - (12 \oplus 8) = 16$$$。

第五个测试用例中有两个正确答案,因为 $$$f(2, 3) = f(3, 4)$$$ 并且它们的长度相等。