Iva & Pav (Codeforces 1878E)
Tags: Greedy, bitmasks

Iva and Pav are a famous Serbian competitive programming couple. In Serbia, they call Pav "papuca" and that's why he will make all of Iva's wishes come true.Iva gave Pav an array $$$a$$$ of $$$n$$$ elements.Let's define $$$f(l, r) = a_l \ \& \ a_{l+1} \ \& \dots \& \ a_r$$$ (here $$$\&$$$ denotes the bitwise AND operation). Note that $$$f(l, r)$$$ is not defined when $$$l>r$$$.Iva also gave Pav $$$q$$$ queries.Each query consists of 2 numbers, $$$k$$$ and $$$l$$$, and she wants Pav to find the largest index $$$r$$$ ($$$l \le r \le n$$$), such that $$$f(l, r) \ge k$$$. Pav wants to solve this problem fast because he doesn't want to upset Iva. He needs your help.

Input: The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the length of array $$$a$$$.The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — the elements of array $$$a$$$.The third line of each test case contains a single integer $$$q$$$ ($$$1 \le q \le 10^5$$$) — the number of queries Iva gave Pav.The next $$$q$$$ lines of each test case contains two numbers, $$$l$$$ and $$$k$$$ ($$$1 \le l \le n$$$, $$$1 \le k \le 10^9$$$) — the left bound for the subsegment, and the integer $$$k$$$ described in statement.It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$. Also, it is guaranteed that the sum of $$$q$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output: For each query output maximal index $$$r$$$ ($$$l \le r \le n$$$) such that $$$a_l \ \& \ a_{l+1} \ \& \dots \& \ a_r \ \ge \ k$$$.If such $$$r$$$ doesn't exist, output $$$-1$$$.

Note: In the first test case $$$n=5$$$, and the array $$$a = [15, 14, 17, 42, 34]$$$The first query asks for the biggest index $$$r$$$ such that the $$$f(1, r) \ge 7$$$.$$$f(1,1) = 15, \ f(1, 2) = 14, \ f(1,3)=0 \ f(1, 4)=0 \ f(1, 5)=0$$$, so $$$r=2$$$ is the answer.The second query asks for $$$f(2, r) \ge 15$$$. Since such $$$r$$$ doesn't exist, the answer is $$$-1$$$.The third query asks for $$$f(4, r) \ge 5$$$. $$$f(4, 4) = 42, \ f(4, 5) = 34$$$, so $$$r=5$$$ is the answer.In the second test case $$$n=5$$$, and the array $$$a= [7, 5, 3, 1, 7]$$$.For the first query, $$$f(1, r) \ge 7$$$.$$$f(1, 1)=7, \ f(1, 2)=5, \ f(1, 3) = 1, \ f(1,4) = 1, \ f(1, 5)=1$$$, so the answer to this query is $$$1$$$.For the second query, $$$f(5, r) \ge 7$$$.$$$f(5, 5) = 7$$$, so the answer is $$$5$$$.For the third query, $$$f(2, r) \ge 3$$$.$$$f(2, 2) = 5, \ f(2, 3) = 1, \ f(2, 4) = 1, \ f(2, 5) = 1$$$, so the answer is $$$2$$$.

Sample Inputs:
3
5
15 14 17 42 34
3
1 7
2 15
4 5
5
7 5 3 1 7
4
1 7
5 7
2 3
2 2
7
19 20 15 12 21 7 11
4
1 15
4 4
7 12
5 7

Sample Outputs:
2 -1 5 
1 5 2 2 
2 6 -1 5

Solution (Python):
t = int(input())
while t > 0:
    t -= 1
    n = int(input())
    a = list(map(int, input().split()))
    sp = [[0] * 20 for _ in range(n + 1)]
    for i in range(n):
        sp[i][0] = a[i]
    for j in range(1, 20):
        for i in range(n - (1 << j) + 1):
            sp[i][j] = sp[i][j - 1] & sp[i + (1 << j - 1)][j - 1]
    q = int(input())
    while q > 0:
        q -= 1
        (l, k) = map(int, input().split())
        l -= 1
        if a[l] < k:
            print(-1, end=' ')
            continue
        cur = a[l]
        l += 1
        for j in range(19, -1, -1):
            if cur & sp[l][j] >= k:
                cur &= sp[l][j]
                l += 1 << j
        print(l, end=' ')
    print()

Solution (Python):
def case():
    n = int(input())
    a = ints()
    q = int(input())
    lk = [ints() for _ in range(q)]
    suffix = build_suffix_array(a)
    return [solve(l - 1, k, suffix, a) for (l, k) in lk]

def solve(l, k, suffix, a):
    max_r = len(suffix[0]) - 1 - l
    best_r = 0
    for b in range(31, -1, -1):
        x = 1 << b
        c = suffix[b][l]
        if x & k == 0:
            best_r = max(best_r, min(c, max_r))
        else:
            max_r = min(max_r, c)
    best_r = max(best_r, max_r)
    return -1 if best_r == 0 else l + best_r

def build_suffix_array(a):
    arr = []
    x = 1
    for _ in range(32):
        line = [0]
        for ai in reversed(a):
            if ai & x:
                line.append(line[-1] + 1)
            else:
                line.append(0)
        arr.append(line[::-1])
        x <<= 1
    return arr

def main():
    for _ in range(int(input())):
        print(*case())

def ints():
    return list(map(int, input().split()))

def floats():
    return list(map(float, input().split()))
if __name__ == '__main__':
    main()
''

Solution (Python):
t = int(input())
while t > 0:
    t -= 1
    n = int(input())
    a = list(map(int, input().split()))
    sp = [[0] * 20 for _ in range(n + 1)]
    for i in range(n):
        sp[i][0] = a[i]
    for j in range(1, 20):
        for i in range(n - (1 << j) + 1):
            sp[i][j] = sp[i][j - 1] & sp[i + (1 << j - 1)][j - 1]
    q = int(input())
    while q > 0:
        q -= 1
        (l, k) = map(int, input().split())
        l -= 1
        if a[l] < k:
            print(-1, end=' ')
            continue
        cur = a[l]
        l += 1
        for j in range(19, -1, -1):
            if cur & sp[l][j] >= k:
                cur &= sp[l][j]
                l += 1 << j
        print(l, end=' ')
    print()