PROBLEM LINK:Author: Vipul Sharma 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 $(x1)^{th}$ version of segment tree. AUTHOR'S AND TESTER'S SOLUTIONS:Author's solution RELATED PROBLEMS:
This question is marked "community wiki".
asked 16 Jun '17, 10:47

i found this to be more clean, detailed and understandable than the above editorial : Unofficial editorial answered 17 Jul '17, 21:28
