Array range queries for elements with frequency same as value

Given an array of N numbers, the task is to answer Q queries of the following type:

query(start, end) = Number of times a 
number x occurs exactly x times in a 
subarray from start to end

Examples:  

Input : arr = {1, 2, 2, 3, 3, 3} 
Query 1: start = 0, end = 1, 
Query 2: start = 1, end = 1, 
Query 3: start = 0, end = 2, 
Query 4: start = 1, end = 3, 
Query 5: start = 3, end = 5, 
Query 6: start = 0, end = 5 
Output : 1 0 2 1 1 3 

Explanation:
In Query 1, Element 1 occurs once in subarray [1, 2]; 
In Query 2, No Element satisfies the required condition is subarray [2]; 
In Query 3, Element 1 occurs once and 2 occurs twice in subarray [1, 2, 2]; 
In Query 4, Element 2 occurs twice in subarray [2, 2, 3]; 
In Query 5, Element 3 occurs thrice in subarray [3, 3, 3]; 
In Query 6, Element 1 occurs once, 2 occurs twice and 3 occurs thrice in subarray [1, 2, 2, 3, 3, 3] 

Method 1 (Brute Force): Calculate frequency of every element in the subarray under each query. If any number x has frequency x in the subarray covered under each query, we increment the counter.  

Implementation:

Answer for Query 1 = 1
Answer for Query 2 = 0
Answer for Query 3 = 2
Answer for Query 4 = 1
Answer for Query 5 = 1
Answer for Query 6 = 3

Time Complexity: O(Q * N)

Auxiliary Space: O(N)

Method 2 (Efficient):

We can solve this problem using the MO’s Algorithm. 

We assign starting index, ending index and query number to each query, Each query takes the following form-

Starting Index(L): Starting Index of the subarray covered under the query; 
Ending Index(R) : Ending Index of the subarray covered under the query; 
Query Number(Index) : Since queries are sorted, this tells us original position of the query so that we answer the queries in the original order

Firstly, we divide the queries into blocks and sort the queries using a custom comparator. 

Now we process the queries offline where we keep two pointers i.e. MO_RIGHT and MO_LEFT with each incoming query, we move these pointers forward and backward and insert and delete elements according to the starting and ending indices of the current query. 
Let the current running answer be current_ans.

Whenever we insert an element we increment the frequency of the included element, if this frequency is equal to the element we just included, we increment the current_ans.If the frequency of this element becomes (current element + 1) this means that earlier this element was counted in the current_ans when it was equal to its frequency, thus we need to decrement current_ans in this case. 

Whenever we delete/remove an element we decrement the frequency of the excluded element, if this frequency is equal to the element we just excluded, we increment the current_ans.If the frequency of this element becomes (current element – 1) this means that earlier this element was counted in the current_ans when it was equal to its frequency, thus we need to decrement current_ans in this case.

Implementation:

Answer for Query 1 = 1
Answer for Query 2 = 0
Answer for Query 3 = 2
Answer for Query 4 = 1
Answer for Query 5 = 1
Answer for Query 6 = 3

Time Complexity of this approach using MO’s Algorithm is O(Q * sqrt(N) * logA) where logA is the complexity to insert an element A into the unordered_map for each query.

Auxiliary Space: O(N+Q)