Sheikh (Easy version) (Codeforces 1732C1)
Tags: Greedy, two pointers

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

Input: 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$$$.

Output: 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.

Note: 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.

Sample Inputs:
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

Sample Outputs:
1 1
1 1
1 1
2 3
2 3
2 4

Solution (Python):
t = int(input())
for _ in range(t):
    (n, q) = map(int, input().split())
    vals = list(map(int, input().split()))
    (L, R) = map(int, input().split())
    L -= 1
    R -= 1
    s = 0
    xr = 0
    for i in range(L, R + 1):
        s += vals[i]
        xr ^= vals[i]
    f = s - xr
    (l, r) = (L, L)
    (ml, mr) = (L, R)
    (curs, curxr) = (0, 0)
    while r <= R:
        curs += vals[r]
        curxr ^= vals[r]
        if curs - curxr == f:
            while l < r and curs - vals[l] - (curxr ^ vals[l]) == f:
                curs -= vals[l]
                curxr ^= vals[l]
                l += 1
            if mr - ml > r - l:
                (mr, ml) = (r, l)
        r += 1
    print(ml + 1, mr + 1)

Solution (Python):
t = int(input())
while t > 0:
    t -= 1
    (n, q) = map(int, input().split())
    a = list(map(int, input().split()))
    ps = [0] * (n + 1)
    px = [0] * (n + 1)
    sum = 0
    x = 0
    for i in range(n):
        sum += a[i]
        x ^= a[i]
        ps[i + 1] = ps[i] + a[i]
        px[i + 1] = px[i] ^ a[i]
    l = 0
    r = n
    ansL = 0
    ansR = n
    while l < r:
        mid = (l + r) // 2
        is_valid = False
        for i in range(n - mid):
            if ps[i + mid + 1] - ps[i] - (px[i + mid + 1] ^ px[i]) == sum - x:
                is_valid = True
                ansL = i
                ansR = i + mid
                break
        if is_valid:
            r = mid
        else:
            l = mid + 1
    while q > 0:
        q -= 1
        (l, r) = map(int, input().split())
        print(ansL + 1, ansR + 1)

Solution (Python):
t = int(input())
for _ in range(t):
    n = int(input().split()[0])
    a = list(map(int, input().split()))
    ps = [0] * (n + 1)
    px = [0] * (n + 1)
    sum = 0
    xor = 0
    for i in range(n):
        sum += a[i]
        xor ^= a[i]
        ps[i + 1] = ps[i] + a[i]
        px[i + 1] = px[i] ^ a[i]
    max_f = sum - xor
    l = 0
    r = n
    ansL = 0
    ansR = n
    while l < r:
        mid = (l + r) // 2
        is_valid = False
        for i in range(n - mid):
            subarray_sum = ps[i + mid + 1] - ps[i]
            subarray_xor = px[i + mid + 1] ^ px[i]
            if subarray_sum - subarray_xor == max_f:
                is_valid = True
                ansL = i
                ansR = i + mid
                break
        if is_valid:
            r = mid
        else:
            l = mid + 1
    input()
    print(ansL + 1, ansR + 1)