PROBLEM LINK:
Author: Parth Mittal
Tester: Satyam Kumar
Editorialist: 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:
ans = -(elements in A <= root(k)) * (elements in B <= root(k))
for i = 1 to root(k):
ans += (elements in A = i) * (elements in B <= K / i)
Note that setting ans to 0 in the beginning will lead to some over-counting, which the current value eliminates.
How do we answer the sub-queries we generate? They can be handled by a Binary Indexed Tree. Note that a segment tree will not work here because of high constant factor.
How do we extend to multiple queries? We can use Mo’s algorithm.
Overall runtime is O(Q\times \sqrt{N}\times \log N + Q\times \sqrt{k}\times \log N).