PROBLEM LINK:
Author: vinod10
Editorialist: vinod10
DIFFICULTY:
Medium
PREREQUISITES:
Sieve of Eratosthenes, MO’s Algorithm.
PROBLEM:
Array of N elements and Q queries are given. Each query consists of a range [l,r]. Answer is number of primes which occur exactly twice in subarray A[l], A[l+1],…, A[r].
QUICK EXPLANATION:
Using Sieve of Eratosthene, precomputation is done to find a number is prime or not. An array is used to keep track of frequency of numbers in the subarray from l to r. Now using MO’s algorithm queries are processed, and required answer is updated accordingly when an element is added/removed from subarray.
EXPLANATION:
If you are not familiar with MO’s algorithm, then you can learn it here.
Array elements can be as large as 106, so sieve is used to precompute primality of every number from 1 to 106. We can store this in boolean array of size 106.
Problem requires direct use of MO’s algorithm, so we sort the queries and start processing them. Now when current range is updated and each time we add or remove number from subarray, we increase(when adding number to subarray) or decrease(when removing number from subarray) the frequency of that number. We only change frequency if the number being added/removed is prime and primality can be checked in O(1) as precomputation is done.
A global variable “ans” is used, which keeps track of primes occuring exactly twice in the subarray.
While adding a number if frequency increases from 1 to 2 then “ans” is incremented by one or if it increases from 2 to 3, then “ans” is decremented by one.
While removing a number if frequency decreases from 3 to 2 then “ans” is incremented by one or if it decreases from 2 to 1, then “ans” is decremented by one.
Time complexity: O((N+Q)N)
AUTHOR’S SOLUTIONS:
Author’s solution can be found here.