309765: CF1732C1. Sheikh (Easy version)
Memory Limit：256 MB
Time Limit：4 S
Judge Style：Text Compare
Creator：
Submit：0
Solved：0
Description
Sheikh (Easy version)
题目描述
This is the easy version of the problem. The only difference is that in this version $ q = 1 $ . You are given an array of integers $ a_1, a_2, \ldots, a_n $ . The cost of a subsegment of the array $ [l, r] $ , $ 1 \leq l \leq r \leq n $ , is the value $ f(l, r) = \operatorname{sum}(l, r) - \operatorname{xor}(l, r) $ , where $ \operatorname{sum}(l, r) = a_l + a_{l+1} + \ldots + a_r $ , and $ \operatorname{xor}(l, r) = a_l \oplus a_{l+1} \oplus \ldots \oplus a_r $ ( $ \oplus $ stands for [bitwise XOR](https://en.wikipedia.org/wiki/Bitwise_operation#XOR)). You will have $ q = 1 $ query. Each query is given by a pair of numbers $ L_i $ , $ R_i $ , where $ 1 \leq L_i \leq R_i \leq n $ . You need to find the subsegment $ [l, r] $ , $ L_i \leq l \leq r \leq R_i $ , with maximum value $ f(l, r) $ . If there are several answers, then among them you need to find a subsegment with the minimum length, that is, the minimum value of $ r - l + 1 $ .输入输出格式
输入格式
Each test consists of multiple test cases. The first line contains an integer $ t $ ( $ 1 \leq t \leq 10^4 $ ) — the number of test cases. The description of test cases follows. The first line of each test case contains two integers $ n $ and $ q $ ( $ 1 \leq n \leq 10^5 $ , $ q = 1 $ ) — the length of the array and the number of queries. The second line of each test case contains $ n $ integers $ a_1, a_2, \ldots, a_n $ ( $ 0 \leq a_i \leq 10^9 $ ) — array elements. $ i $ -th of the next $ q $ lines of each test case contains two integers $ L_i $ and $ R_i $ ( $ 1 \leq L_i \leq R_i \leq n $ ) — the boundaries in which we need to find the segment. It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 2 \cdot 10^5 $ . It is guaranteed that $ L_1 = 1 $ and $ R_1 = n $ .
输出格式
For each test case print $ q $ pairs of numbers $ L_i \leq l \leq r \leq R_i $ such that the value $ f(l, r) $ is maximum and among such the length $ r - l + 1 $ is minimum. If there are several correct answers, print any of them.
输入输出样例
输入样例 #1
6
1 1
0
1 1
2 1
5 10
1 2
3 1
0 2 4
1 3
4 1
0 12 8 3
1 4
5 1
21 32 32 32 10
1 5
7 1
0 1 0 1 0 1 0
1 7输出样例 #1
1 1
1 1
1 1
2 3
2 3
2 4说明
In the first test case, $ f(1, 1) = 0 - 0 = 0 $ . In the second test case, $ f(1, 1) = 5 - 5 = 0 $ , $ f(2, 2) = 10 - 10 = 0 $ . Note that $ f(1, 2) = (10 + 5) - (10 \oplus 5) = 0 $ , but we need to find a subsegment with the minimum length among the maximum values of $ f(l, r) $ . So, only segments $ [1, 1] $ and $ [2, 2] $ are the correct answers. In the fourth test case, $ f(2, 3) = (12 + 8) - (12 \oplus 8) = 16 $ . There are two correct answers in the fifth test case, since $ f(2, 3) = f(3, 4) $ and their lengths are equal.Input
题意翻译
$q$ 次询问，每次求 $[L, R]$ 内任意子区间的和减去该区间的异或值得到的差的最大值，若有多个最大值，取区间长度最短的，若仍有多个区间，任取一个输出即可。在简单版本中，保证 $q = 1$，$L$ = 1，$R = n$。Output
### 题目：谢赫（简单版本）
#### 题目描述
这个问题的简单版本。唯一的不同是，在这个版本中 $ q = 1 $。
给你一个整数数组 $ a_1, a_2, \ldots, a_n $。
数组 $ [l, r] $ 的子段成本是值 $ 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 = 1 $ 查询。每个查询由一对数字 $ 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 = 1 $）——数组的长度和查询的数量。
每个测试案例的第二行包含 $ 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 1
5 10
1 2
3 1
0 2 4
1 3
4 1
0 12 8 3
1 4
5 1
21 32 32 32 10
1 5
7 1
0 1 0 1 0 1 0
1 7
```
##### 输出样例 #1
```
1 1
1 1
1 1
2 3
2 3
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) $ 并且它们的长度相等。### 题目：谢赫（简单版本） #### 题目描述 这个问题的简单版本。唯一的不同是，在这个版本中 $ q = 1 $。 给你一个整数数组 $ a_1, a_2, \ldots, a_n $。 数组 $ [l, r] $ 的子段成本是值 $ 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 = 1 $ 查询。每个查询由一对数字 $ 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 = 1 $）——数组的长度和查询的数量。 每个测试案例的第二行包含 $ 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 1 5 10 1 2 3 1 0 2 4 1 3 4 1 0 12 8 3 1 4 5 1 21 32 32 32 10 1 5 7 1 0 1 0 1 0 1 0 1 7 ``` ##### 输出样例 #1 ``` 1 1 1 1 1 1 2 3 2 3 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) $ 并且它们的长度相等。
#### 题目描述
这个问题的简单版本。唯一的不同是，在这个版本中 $ q = 1 $。
给你一个整数数组 $ a_1, a_2, \ldots, a_n $。
数组 $ [l, r] $ 的子段成本是值 $ 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 = 1 $ 查询。每个查询由一对数字 $ 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 = 1 $）——数组的长度和查询的数量。
每个测试案例的第二行包含 $ 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 1
5 10
1 2
3 1
0 2 4
1 3
4 1
0 12 8 3
1 4
5 1
21 32 32 32 10
1 5
7 1
0 1 0 1 0 1 0
1 7
```
##### 输出样例 #1
```
1 1
1 1
1 1
2 3
2 3
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) $ 并且它们的长度相等。### 题目：谢赫（简单版本） #### 题目描述 这个问题的简单版本。唯一的不同是，在这个版本中 $ q = 1 $。 给你一个整数数组 $ a_1, a_2, \ldots, a_n $。 数组 $ [l, r] $ 的子段成本是值 $ 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 = 1 $ 查询。每个查询由一对数字 $ 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 = 1 $）——数组的长度和查询的数量。 每个测试案例的第二行包含 $ 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 1 5 10 1 2 3 1 0 2 4 1 3 4 1 0 12 8 3 1 4 5 1 21 32 32 32 10 1 5 7 1 0 1 0 1 0 1 0 1 7 ``` ##### 输出样例 #1 ``` 1 1 1 1 1 1 2 3 2 3 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) $ 并且它们的长度相等。