PROBLEM LINK:
Author: Teja Vardhan Reddy
Tester: Aswin Ashok
Editorialist: Aswin Ashok
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 5-3=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.
Since in the constraints it is given that the difference between the Max and Min of array a is less than 10^5+200. So we can find all primes in the range [Min_a,Max_a] using segmented Sieve or Rabin Miller and store it in an array.
We can also find and store the nearest smaller prime for each number in the range [3,2000]
Now we have to maintain two segment trees one with sum and other one with Maximum value of the range.
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.