PROBLEM LINK:Author: Teja Vardhan Reddy DIFFICULTY:MEDIUM PREREQUISITES:Segment Tree, Segmented Sieve or Rabin Miller Primality Test, Prime Gap PROBLEM:You are given an array a (1 indexed)of size n. You have to process following operations on the array 1 l r : update elements of indices from l to r inclusive to difference of element and nearest strictly smaller prime (eg: 5 gets updated to 53=2). Also note that since 0,1,2 does not have primes below then even after update they remain the same. 2 l r : Find Sum of elements of array from l to r indices EXPLANATION:After first update each updated element becomes less than 2000 since the prime gap is less than 2000 for given range of input. When we are updating if the leaf node in the segment tree is greater than 2000 we can do a binary search in array of primes to find the next smaller prime but if the leaf node is less than 2000 we already we know its nearest smaller prime. Once the nearest smaller prime is found update the leaf node and the nodes above. One thing to note is that we need not update the elements less than three so if the maximum element of range is 3 we need not update it at all To find the sum we can directly query on sum segment tree. SOLUTIONS:Solution can be found here.
This question is marked "community wiki".
asked 02 Jun '18, 21:24

Hello,I am a school student , the maths requried for LOC is of a bit high level. I would be grateful if u all can suggest tutorials or books from which I can study:)@aswinashok44 @teja349 answered 01 Jul '18, 18:43
Hello Krish, LoC has become a little harder over the past two years. We are trying to find the correct difficulty for school students. Hope the last session was easier. I would suggest you to practice hard and learn from online forums like this, codechef and codeforces blogs are a good source of information.
(06 Jul '18, 13:29)
Yep the last session was easier:) But finding proper material to pratice from is though.Can u plz suggest the list of books or websites specifically . Even for MATHS. Thanks in advance.
(09 Jul '18, 23:27)
(02 Aug '18, 22:33)
