PROBLEM LINK:Author: Parth Mittal DIFFICULTY:MEDIUM PREREQUISITES:Binary Indexed Tree, Offline Algorithms PROBLEM:You are given two arrays, $A$ and $B$, both of size $N$. You are given $Q$ queries of the form $(i, j, k)$. Where for each query, you have to find the cardinality of the multiset $S(i,j,k) = \{A_p \cdot B_q  i \leq p,q \leq j, A_p \cdot B_q ≤ k\}$. EXPLANATION:Note that we're looking for pairs $(p, q)$, such that $p\times q \leq k$. This implies that at least one of $p$ or $q$ is $\leq \sqrt{k}$. This gives us an algorithm to answer a single query:
Note that setting $ans$ to $0$ in the beginning will lead to some overcounting, which the current value eliminates.
This question is marked "community wiki".
asked 12 Oct '16, 23:01
