Sheikh (Hard Version) (Codeforces 1732C2)
Tags: Greedy, two pointers

This is the hard version of the problem. The only difference is that in this version $$$q = n$$$.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$$$ queries. 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 = n$$$) — 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 all test cases, the first query is considered.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 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

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

Solution (Python):
import os, sys
from io import BytesIO, IOBase

def read_ls(func=int):
    return list(map(func, input().split(' ')))

def solve(n, q, a, qs):
    l2r = []
    last_nonzero = -1
    for (i, x) in enumerate(a):
        if x != 0:
            last_nonzero = i
        l2r.append(last_nonzero)
    r2l = [-1] * n
    last_nonzero = n
    for i in range(n - 1, -1, -1):
        if a[i] != 0:
            last_nonzero = i
        r2l[i] = last_nonzero
    pref = []
    cur = 0
    for x in a:
        cur = cur ^ x
        pref.append(cur)
    pref.append(0)
    for (l, r) in qs:
        l0 = l
        l = r2l[l]
        r = l2r[r]
        if l > r:
            print(l0 + 1, l0 + 1)
            continue
        tot = pref[r] ^ pref[l - 1]
        best = [l, r]
        cur = l
        bad = False
        while True:
            cur = r2l[cur]
            if cur > r:
                print(l0 + 1, l0 + 1)
                bad = True
                break
            k = r
            temp = tot
            while k > cur and temp & a[k] == a[k]:
                temp = temp ^ a[k]
                if a[k] == 0:
                    k = l2r[k]
                else:
                    k -= 1
            if cur > k:
                print(l0 + 1, l0 + 1)
                bad = True
                break
            if k - cur < best[1] - best[0]:
                best = [cur, k]
            if cur < r and tot & a[cur] == a[cur]:
                tot = tot ^ a[cur]
                cur += 1
            else:
                break
        if not bad:
            print('{} {}'.format(best[0] + 1, best[1] + 1))

def main():
    for _ in range(int(input())):
        (n, q) = read_ls()
        a = read_ls()
        qs = [read_ls(lambda s: int(s) - 1) for _ in range(q)]
        solve(n, q, a, qs)
BUFSIZE = 8192

class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = 'x' in file.mode or 'r' not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b'\n') + (not b)
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            (self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode('ascii'))
        self.read = lambda : self.buffer.read().decode('ascii')
        self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
if __name__ == '__main__':
    main()

Solution (Python):
import io, os
import bisect
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def main(t):
    (n, q) = map(int, input().split())
    arr = list(map(int, input().split()))
    accusum = [0] * (n + 1)
    accuxor = [0] * (n + 1)
    accu = [[0] * 30 for _ in range(n + 1)]
    for i in range(n):
        accusum[i] = accusum[i - 1] + arr[i]
        accuxor[i] = accuxor[i - 1] ^ arr[i]

    def findvalue(l, r):
        return accusum[r] - accusum[l - 1] - (accuxor[r] ^ accuxor[l - 1])
    nonzero = []
    for i in range(n):
        if arr[i] > 0:
            nonzero.append(i)
    for _ in range(q):
        (l, r) = map(int, input().split())
        l -= 1
        r -= 1
        target = findvalue(l, r)
        if target == 0:
            print(l + 1, l + 1)
            continue
        locleft = bisect.bisect_left(nonzero, l)
        locright = bisect.bisect(nonzero, r) - 1
        minlength = nonzero[locright] - nonzero[locleft] + 1
        ans = [nonzero[locleft], nonzero[locright]]
        front = locleft
        for rear in range(max(locright - 32, locleft), locright + 1):
            if findvalue(nonzero[front], nonzero[rear]) < target:
                continue
            while findvalue(nonzero[front + 1], nonzero[rear]) == target:
                front += 1
            if nonzero[rear] - nonzero[front] + 1 < minlength:
                ans = [nonzero[front], nonzero[rear]]
                minlength = nonzero[rear] - nonzero[front] + 1
        print(ans[0] + 1, ans[1] + 1)
T = int(input())
t = 1
while t <= T:
    main(t)
    t += 1

Solution (Python):
import sys
input = sys.stdin.readline
inf = float('inf')

def getInt():
    return int(input())

def getStr():
    return input().strip()

def getList(split=True):
    s = getStr()
    if split:
        s = s.split()
    return map(int, s)
t = getInt()

def solve():
    (n, q) = getList()
    a = list(getList())
    p = [0] * (n + 1)
    xor = [0] * (n + 1)
    from bisect import bisect_left, bisect
    zeroes = []
    nonZeroes = []
    for (i, j) in enumerate(a, 1):
        p[i] = p[i - 1] + j
        xor[i] = xor[i - 1] ^ j
        if j:
            nonZeroes.append(i)
        else:
            zeroes.append(i)

    def getRange(l, r):
        return p[r] - p[l - 1] - (xor[r] ^ xor[l - 1])
    for _ in range(q):
        (l, r) = getList()
        expected = getRange(l, r)
        it = bisect_left(zeroes, l)
        if expected == 0 and it < len(zeroes) and (zeroes[it] <= r):
            print(zeroes[it], zeroes[it])
        else:
            L = bisect_left(nonZeroes, l)
            R = bisect(nonZeroes, r) - 1
            (x, y) = (l, r)
            for L in range(L, min(len(nonZeroes), L + 32)):
                if nonZeroes[L] > r:
                    break
                for i in range(R, -1, -1):
                    if nonZeroes[L] > nonZeroes[i]:
                        break
                    e = getRange(nonZeroes[L], nonZeroes[i])
                    if e != expected:
                        break
                    if nonZeroes[i] - nonZeroes[L] < y - x:
                        (x, y) = (nonZeroes[L], nonZeroes[i])
                L += 1
            print(x, y)
for _ in range(t):
    solve()
''