PROBLEM LINK:
Author: Vipul Sharma
Tester: Prateek Gupta
Editorialist: Oleksandr Kulkov
DIFFICULTY:
MEDIUM
PREREQUISITES:
Segment tree
PROBLEM:
You are given array of n integers and q queries. For each query you have to sum up number of times prime numbers from [x;y] occur in elements of a from [l;r].
EXPLANATION:
Any number C consists of at most O(\log C) distinct prime divisors. We can keep all this divisors in segment tree and ask queries of kind how many numbers are there on segment [l;r] such that x \leq a[i] \leq y. We have total of O(n \log C) numbers in segment tree. Now we can answer those queries in O((\log{(n \log C)})^2) per query with if we keep in each vertex of segment tree sorted array of numbers which occur on its segment.
We can answer a query in \mathcal{O}(\log{(n \log C)}) time by using persistent segment tree. For each prime x from 2 to max(A_i), we will maintain a version of segment tree, which the version y can tell the answer for query (1, y) for some given [l, r]. We can maintain these versions of the segment trees using persistent segment tree. The answer for query [x, y] and [l, r] will be answer of query [l, r] in y-th version of the segment tree subtracted by answer of the query [l, r] in the (x-1)^{th} version of segment tree.
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution
Tester’s solution