PROBLEM LINK:
Author: Suraj Kumar
Tester: Rishabh Gupta
Editorialist: Suraj Kumar
DIFFICULTY:
MEDIUM
PREREQUISITES:
Data Structure, Segment tree, Sieve of Eratothenes
PROBLEM:
You are given an array of N inegers on which you have to perform
Q queries which can be of update type in which you need to change
the content at index i with X.
The other type of query is to count the total number of primes
between a given range of indices L and R.
QUICK EXPLANATION:
Find an efficient way to tell the no. of prime numbers between
two given indices of an Array.
EXPLANATION:
The problem is pretty straightforward.
First of all we need to find all the prime numbers from 1 to
100000, which can be done using the sieve.
After this is done we need to build the segment tree, which
can be done in order of nlogn.
After the tree is built we simply need to query the tree for
each of the query of first type in order of logn.
For the update query we need to change only those part of the
tree which will be affected by this update. This can also be
done in logn.
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here.
Tester’s solution can be found here.