You are not logged in. Please login at www.codechef.com to post your questions!

×

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:

This question is marked "community wiki".

asked 16 Jun '17, 10:47

melfice's gravatar image

4★melfice
811837
accept rate: 0%

edited 21 Nov '17, 16:31

admin's gravatar image

0★admin ♦♦
19.8k350498541


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

link

answered 17 Jul '17, 21:28

scorpion_ajay's gravatar image

4★scorpion_ajay
232
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×15,639
×2,589
×1,755
×149
×13

question asked: 16 Jun '17, 10:47

question was seen: 2,511 times

last updated: 21 Nov '17, 16:31