DDCC - Editorial

PROBLEM LINK:

Practice
Contest

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:

  1. The elements of the array do not change at any point of time.
  2. The size of the array remains same.
  3. 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.

SIMILAR PROBLEMS:

DQUERY - SPOJ

PROBLEM CREDITS:

Codeforces

3 Likes

Can anyone help me in figuring out why this submission gives a runtime error ?

Thanks!

1 Like

My soln is almost same as the solution provided… But it is giving TLE. Please tell if I am missing something.
https://www.codechef.com/viewsolution/9929712

The Author’s solution is also giving Time Limit Exceeded. The same is getting accepted on codeforces (link mentioned under problem credits). Please review the constraint.
Thanks