PROBLEM LINK:
Author: sahilarora.535
DIFFICULTY:
MEDIUM
PREREQUISITES:
Mo’s Algorithm
PROBLEM:
Given an array with N integers and Q queries, for each query we get integers L and R. Find the number of occurences of each distinct number in the range L to R inclusive, and output the answer for the query = summation(K*K*C), where K is the count of distinct integer, and C is the distinct integer.
EXPLANATION:
Going by the naive solution, for each query we can create a set which contains the distinct elements, and for every element which we encounter, increase it’s count by 1 each time we encounter the element in the segment. So every query can be done in O(N) time. So total time complexity of the naive solution = O(N*Q). But this will surely give a TLE.
Points to note:
- The elements of the array do not change at any point of time.
- The size of the array remains same.
- The queries can be solved in any order.
These points give us a hint that the problem can be solved via an offline algorithm, i.e. MO’s algorithm. We need to sort the queries in such a way that they become beneficial for us. For a tutorial on MO’s algorithm, read here:
MO’s Algorithm - Blog by Anudeep Nekkanati
After reading the tutorial and editing the code provided according to the need, the problem can be solved in O(N*sqrt(N)).
AUTHOR’S SOLUTIONS:
Author’s solution can be found here.