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. RELATED PROBLEMS:asked 24 Jan '17, 18:59
