temp1967's blog

OR subarray
By temp1967, history, 4 weeks ago, In English

Given an array of size n and there are q queries with each query having a value. Want to find number of subarrays with or equal to the query value. 1<=n<=10^5; 1<=q<=10^5; A small hint I know was number of distinct or values in a subarray is 32*n; please prove it also.

  • Vote: I like it
  • -4
  • Vote: I do not like it

»
4 weeks ago, # |
  Vote: I like it +5 Vote: I do not like it

You didn't give the bounds of $$$a_i$$$ so I assume that $$$a_i \le 10^9$$$. Now $$$a_i$$$ has at most $$$31$$$ bits in binary.

Let's define $$$f(l,r)$$$ as the or sum of subarray $$$a[l,r]$$$. Consider $$$f(l,r)$$$ and $$$f(l,r+1)$$$, for each $$$j \in [0,31]$$$, $$$f(l,r+1)$$$'s $$$j$$$ -th bit is not smaller than $$$f(l,r)$$$'s, so there are at most $$$\mathcal O(\log V)$$$ distinct values of in $$$f(l,l),f(l,l+1),\ldots,f(l,n)$$$.

Now let's do binary search for each $$$l$$$. Since there $$$\mathcal O(\log V)$$$ distinct value, let binary search the start point $$$ql$$$ and the end point $$$qr$$$ for each possible value $$$x$$$. That is, $$$\forall j \in [ql,qr], f(l,j) = x$$$.

Now we just need to calculate $$$f(l,r)$$$ quickly to do the binary search and I believe you know how to calculate this in $$$\mathcal O(n \log n) - \mathcal O(1)$$$.

→ Reply
»
4 weeks ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Similar to this problems
https://leetcode.com/problems/bitwise-ors-of-subarrays/description/
Solve by checking all subarrays

→ Reply