Bitwise AND Over Range
Python
Hard
3 views
Problem Description
Read n integers and q queries (l r). For each query output bitwise AND of a[l..r] (1-based).
Input Format
First line n q. Second line n integers. Next q lines: l r.
Output Format
q lines answers.
Sample Test Case
Input:
5 2
7 3 15 8 10
1 3
2 5
Official Solution
import sys
data=sys.stdin.read().strip().split()
if not data: sys.exit(0)
it=iter(data)
n=int(next(it)); q=int(next(it))
a=[int(next(it)) for _ in range(n)]
LOG=0
while (1<<LOG) <= n:
LOG+=1
st=[a[:]]
for k in range(1,LOG):
prev=st[k-1]
ln=n-(1<<k)+1
cur=[0]*ln
half=1<<(k-1)
for i in range(ln):
cur[i]=prev[i] & prev[i+half]
st.append(cur)
out=[]
for _ in range(q):
l=int(next(it))-1
r=int(next(it))-1
length=r-l+1
k=(length.bit_length()-1)
out.append(str(st[k][l] & st[k][r-(1<<k)+1]))
sys.stdout.write('\
'.join(out))
Solutions (0)
No solutions submitted yet. Be the first!
No comments yet. Start the discussion!