A15456. 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$ .
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$ .
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.
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.