这是问题的困难版本。唯一的区别是在这个版本中 $$$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)$$$ 并且它们的长度相等。