And Reachability (Codeforces 1168C)
Tags: DP, bitmasks

Toad Pimple has an array of integers $$$a_1, a_2, \ldots, a_n$$$.We say that $$$y$$$ is reachable from $$$x$$$ if $$$x<y$$$ and there exists an integer array $$$p$$$ such that $$$x = p_1 < p_2 < \ldots < p_k=y$$$, and $$$a_{p_i}\, \&\, a_{p_{i+1}} > 0$$$ for all integers $$$i$$$ such that $$$1 \leq i < k$$$.Here $$$\&$$$ denotes the bitwise AND operation.You are given $$$q$$$ pairs of indices, check reachability for each of them.

Input: The first line contains two integers $$$n$$$ and $$$q$$$ ($$$2 \leq n \leq 300\,000$$$, $$$1 \leq q \leq 300\,000$$$) — the number of integers in the array and the number of queries you need to answer.The second line contains $$$n$$$ space-separated integers $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \leq a_i \leq 300\,000$$$) — the given array.The next $$$q$$$ lines contain two integers each. The $$$i$$$-th of them contains two space-separated integers $$$x_i$$$ and $$$y_i$$$ ($$$1 \leq x_i < y_i \leq n$$$). You need to check if $$$y_i$$$ is reachable from $$$x_i$$$. 

Output: Output $$$q$$$ lines. In the $$$i$$$-th of them print "Shi" if $$$y_i$$$ is reachable from $$$x_i$$$, otherwise, print "Fou".

Note: In the first example, $$$a_3 = 0$$$. You can't reach it, because AND with it is always zero. $$$a_2\, \&\, a_4 > 0$$$, so $$$4$$$ is reachable from $$$2$$$, and to go from $$$1$$$ to $$$4$$$ you can use $$$p = [1, 2, 4]$$$.

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

Sample Outputs:
Fou
Shi
Shi

Solution (Python):
import sys, os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
(n, q) = map(int, input().split())
a = [0] + list(map(int, input().split()))
pow2 = [1]
for _ in range(19):
    pow2.append(2 * pow2[-1])
dp = []
inf = pow(10, 9) + 1
la = [inf] * 19
x = [0] * (n + 1)
for i in range(n, 0, -1):
    ai = a[i]
    dpi = [inf] * 19
    for j in range(19):
        if not ai & pow2[j]:
            continue
        dpi[j] = i
        if la[j] ^ inf and x[la[j]] ^ i:
            dpi = [min(k, l) for (k, l) in zip(dpi, dp[n - la[j]])]
            x[la[j]] = i
        la[j] = i
    dp.append(dpi)
dp.append([0] * 19)
dp.reverse()
ans = []
for _ in range(q):
    (x, y) = map(int, input().split())
    (dpx, ay) = (dp[x], a[y])
    ans0 = 'Fou'
    for i in range(19):
        if not ay & pow2[i]:
            continue
        if dpx[i] <= y:
            ans0 = 'Shi'
            break
    ans.append(ans0)
sys.stdout.write('\n'.join(ans))

Solution (Python):
from bisect import bisect_left as bl
from bisect import bisect_right as br
from heapq import heappush, heappop
import math
from collections import *
from functools import reduce, cmp_to_key, lru_cache
import io, os
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
M = mod = 10 ** 9 + 7

def factors(n):
    return sorted(set(reduce(list.__add__, ([i, n // i] for i in range(1, int(n ** 0.5) + 1) if n % i == 0))))

def inv_mod(n):
    return pow(n, mod - 2, mod)

def li():
    return [int(i) for i in input().rstrip().split()]

def st():
    return str(input().rstrip())[2:-1]

def val():
    return int(input().rstrip())

def li2():
    return [str(i)[2:-1] for i in input().rstrip().split()]

def li3():
    return [int(i) for i in st()]
he = []
(n, q) = li()
queue = [-1] * 20
ans = [[-1] * 20 for i in range(n + 1)]
l = li()
for (i, curr) in enumerate(l):
    for j in range(20):
        if curr >> j & 1:
            for k in range(20):
                ans[i][k] = max(ans[i][k], ans[queue[j]][k])
            ans[i][j] = i
    for j in range(20):
        queue[j] = max(queue[j], ans[i][j])
for i in range(q):
    (a, b) = li()
    a -= 1
    b -= 1
    currans = 0
    for j in range(20):
        if l[a] >> j & 1 and ans[b][j] >= a:
            currans = 1
            break
    print('Shi' if currans else 'Fou')

Solution (Python):
from bisect import bisect_left as bl
from bisect import bisect_right as br
from heapq import heappush, heappop
import math
from collections import *
from functools import reduce, cmp_to_key, lru_cache
import io, os
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
M = mod = 10 ** 9 + 7

def factors(n):
    return sorted(set(reduce(list.__add__, ([i, n // i] for i in range(1, int(n ** 0.5) + 1) if n % i == 0))))

def inv_mod(n):
    return pow(n, mod - 2, mod)

def li():
    return [int(i) for i in input().rstrip().split()]

def st():
    return str(input().rstrip())[2:-1]

def val():
    return int(input().rstrip())

def li2():
    return [str(i)[2:-1] for i in input().rstrip().split()]

def li3():
    return [int(i) for i in st()]
he = []
(n, q) = li()
queue = [-1] * 20
ans = [[-1] * 20 for i in range(n + 1)]
l = li()
for (i, curr) in enumerate(l):
    for j in range(20):
        if curr >> j & 1:
            for k in range(20):
                ans[i][k] = max(ans[i][k], ans[queue[j]][k])
            ans[i][j] = i
    for j in range(20):
        queue[j] = max(queue[j], ans[i][j])
queries = []
for i in range(q):
    queries.append(li())
for i in range(q):
    (a, b) = queries[i]
    a -= 1
    b -= 1
    currans = 0
    for j in range(20):
        if l[a] >> j & 1 and ans[b][j] >= a:
            currans = 1
            break
    print('Shi' if currans else 'Fou')