PRMQ - Editorial

PROBLEM LINK:

Practice
Contest

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

RELATED PROBLEMS:

i found this to be more clean, detailed and understandable than the above editorial : Unofficial editorial

3 Likes