Блог пользователя temp1967

Автор temp1967, история, 6 месяцев назад, По-английски

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.

  • Проголосовать: нравится
  • -4
  • Проголосовать: не нравится

»
6 месяцев назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

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)$$$.

»
6 месяцев назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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