MinimizOR (Codeforces 1665E)
Tags: Greedy, divide and conquer

You are given an array $$$a$$$ of $$$n$$$ non-negative integers, numbered from $$$1$$$ to $$$n$$$.Let's define the cost of the array $$$a$$$ as $$$\displaystyle \min_{i \neq j} a_i | a_j$$$, where $$$|$$$ denotes the bitwise OR operation.There are $$$q$$$ queries. For each query you are given two integers $$$l$$$ and $$$r$$$ ($$$l < r$$$). For each query you should find the cost of the subarray $$$a_{l}, a_{l + 1}, \ldots, a_{r}$$$.

Input: Each test case consists of several test cases. 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 an integer $$$n$$$ ($$$2 \le n \le 10^5$$$) — the length array $$$a$$$.The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i < 2^{30}$$$) — the elements of $$$a$$$.The third line of each test case contains an integer $$$q$$$ ($$$1 \le q \le 10^5$$$) — the number of queries.Each of the next $$$q$$$ lines contains two integers $$$l_j$$$, $$$r_j$$$ ($$$1 \le l_j < r_j \le n$$$) — the description of the $$$j$$$-th query.It is guaranteed that the sum of $$$n$$$ and the sum of $$$q$$$ over all test cases do not exceed $$$10^5$$$.

Output: For each test case print $$$q$$$ numbers, where the $$$j$$$-th number is the cost of array $$$a_{l_j}, a_{l_j + 1}, \ldots, a_{r_j}$$$.

Note: In the first test case the array $$$a$$$ is$$$110_2, 001_2, 011_2, 010_2, 001_2$$$.That's why the answers for the queries are:  $$$[1; 2]$$$: $$$a_1 | a_2 = 110_2 | 001_2 = 111_2 = 7$$$;  $$$[2; 3]$$$: $$$a_2 | a_3 = 001_2 | 011_2 = 011_2 = 3$$$;  $$$[2; 4]$$$: $$$a_2 | a_3 = a_3 | a_4 = a_2 | a_4 = 011_2 = 3$$$;  $$$[2; 5]$$$: $$$a_2 | a_5 = 001_2 = 1$$$. In the second test case the array $$$a$$$ is$$$00_2, 10_2, 01_2, \underbrace{11\ldots 1_2}_{30}$$$ ($$$a_4 = 2^{30} - 1$$$).That's why the answers for the queries are:  $$$[1; 2]$$$: $$$a_1 | a_2 = 10_2 = 2$$$;  $$$[2; 3]$$$: $$$a_2 | a_3 = 11_2 = 3$$$;  $$$[1; 3]$$$: $$$a_1 | a_3 = 01_2 = 1$$$;  $$$[3; 4]$$$: $$$a_3 | a_4 = 01_2 | \underbrace{11\ldots 1_2}_{30} = 2^{30} - 1 = 1073741823$$$. 

Sample Inputs:
2
5
6 1 3 2 1
4
1 2
2 3
2 4
2 5
4
0 2 1 1073741823
4
1 2
2 3
1 3
3 4

Sample Outputs:
7
3
3
1
2
3
1
1073741823

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

def sparse_table(a):
    table = []
    (s0, l) = (a, 1)
    table.append(s0)
    while 2 * l <= len(a):
        s = [min(s0[i], s0[i + l]) for i in range(len(s0) - l)]
        table.append(list(s))
        s0 = s
        l *= 2
    return table

def get_min(l, r, table):
    d = (r - l + 1).bit_length() - 1
    ans = min(table[d][l], table[d][r - pow2[d] + 1])
    return ans
t = int(input())
ans = []
pow2 = [1]
for _ in range(20):
    pow2.append(2 * pow2[-1])
inf = pow(2, 30) + 1
for _ in range(t):
    n = int(input())
    a = [0] + list(map(int, input().split()))
    for i in range(1, n + 1):
        a[i] *= n + 1
        a[i] += i
    table = sparse_table(a)
    q = int(input())
    for _ in range(q):
        (l, r) = map(int, input().split())
        ans0 = inf
        h = []
        heapq.heappush(h, (get_min(l, r, table), l, r))
        x = []
        while len(h) and h[0][0] // (n + 1) < ans0:
            (c, l, r) = heapq.heappop(h)
            z = c // (n + 1)
            c %= n + 1
            for i in x:
                ans0 = min(ans0, i | z)
            x.append(z)
            if l ^ c:
                heapq.heappush(h, (get_min(l, c - 1, table), l, c - 1))
            if c ^ r:
                heapq.heappush(h, (get_min(c + 1, r, table), c + 1, r))
        ans.append(ans0)
sys.stdout.write('\n'.join(map(str, ans)))

Solution (Python):
class SegmentTree:

    def __init__(self, n, oper, e):
        self.n = n
        self.oper = oper
        self.e = e
        self.log = (n - 1).bit_length()
        self.size = 1 << self.log
        self.data = [e] * (2 * self.size)

    def update(self, k):
        self.data[k] = self.oper(self.data[2 * k], self.data[2 * k + 1])

    def build(self, arr):
        for i in range(self.n):
            self.data[self.size + i] = arr[i]
        for i in range(self.size - 1, 0, -1):
            self.update(i)

    def set(self, p, x):
        p += self.size
        self.data[p] = x
        for i in range(self.log):
            p >>= 1
            self.update(p)

    def get(self, p):
        return self.data[p + self.size]

    def prod(self, l, r):
        sml = smr = self.e
        l += self.size
        r += self.size
        while l < r:
            if l & 1:
                sml = self.oper(sml, self.data[l])
                l += 1
            if r & 1:
                r -= 1
                smr = self.oper(self.data[r], smr)
            l >>= 1
            r >>= 1
        return self.oper(sml, smr)
kmax = 31

def op(a1, a2):
    a = [0] * kmax
    i = j = 0
    while i + j < kmax:
        if a1[i] <= a2[j]:
            a[i + j] = a1[i]
            i += 1
        else:
            a[i + j] = a2[j]
            j += 1
    return a
inf = (1 << 30) - 1

def solve():
    n = int(input())
    arr = list(map(int, input().split()))
    seg = SegmentTree(n, op, [inf] * kmax)
    seg.build([[a] + [inf] * (kmax - 1) for a in arr])
    for _ in range(int(input())):
        (l, r) = map(int, input().split())
        a = seg.prod(l - 1, r)
        ans = inf
        for i in range(kmax):
            for j in range(i + 1, kmax):
                ans = min(ans, a[i] | a[j])
        print(ans)
import os
import sys
from io import BytesIO, IOBase
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')
t = int(input())
for i in range(t):
    solve()

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

class Trienode(object):

    def __init__(self):
        self.indexes = []
        self.children = {}

def construct(i, num, root):
    p = root
    for d in range(29, -1, -1):
        digit = 0
        if 1 << d & num > 0:
            digit = 1
        if 0 not in p.children:
            p.children[0] = Trienode()
        if 1 not in p.children:
            p.children[1] = Trienode()
        p = p.children[digit]
        p.indexes.append(i)
    return root

def query(root, front, rear, arr):
    p = root
    output = 0
    addi = []
    curr = 0
    ans = 2147483647
    for d in range(29, -1, -1):
        if len(p.children) > 0:
            temp = p.children[0].indexes
            f0 = bisect.bisect_left(temp, front)
            l = len(temp)
            if f0 + 1 < l and temp[f0 + 1] <= rear:
                p = p.children[0]
            elif f0 < l and temp[f0] <= rear:
                addi.append(temp[f0])
                p = p.children[1]
                curr += 1 << d
            else:
                p = p.children[1]
                curr += 1 << d
        else:
            break
    f = bisect.bisect_left(p.indexes, front)
    r = bisect.bisect(p.indexes, rear)
    if f != r:
        ans = curr
        for i in range(len(addi)):
            ans = min(ans, arr[addi[i]] | curr)
    for i in range(len(addi) - 1):
        for j in range(i + 1, len(addi)):
            ans = min(ans, arr[addi[i]] | arr[addi[j]])
    return ans

def main(t):
    n = int(input())
    arr = list(map(int, input().split()))
    root = Trienode()
    for i in range(n):
        construct(i, arr[i], root)
    q = int(input())
    for r in range(q):
        (front, rear) = map(int, input().split())
        ans = query(root, front - 1, rear - 1, arr)
        if r > 100000:
            break
        os.sys.stdout.write(str(ans) + '\n')
T = int(input())
t = 1
while t <= T:
    main(t)
    t += 1