### 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 =

*. But this will surely give a TLE.*

**O(N*Q)****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.