DQUERY - SPOJ

Prerequisite

Mo’s Algorithm: The basic principle of Mo’s Algorithm is to compute all the queries in such a way so that the result of the current query can be used in the next query.  

Intuition

The above problem can be done with a brute force approach where we will be running a loop to iterate through the array Arr[] in every query to find out the distinct elements in the current range. But this approach would be very expensive with respect to time as the time complexity would be O(N * Q).

So here comes the role of Mo’s Algorithm. Mo’s Algorithm helps us pre-process all the queries in a precise manner such that the result of each query is helpful for the next query.

Also see, Introduction to JQuery

Approach

In Mo’s Algorithm we will follow the below approach:

• After taking input of all the queries, we will try to divide them into blocks of size ‘√N’ such that queries with ‘l’ values from 0 to √N - 1 are together, then from ‘√N’ to ‘2*√N -1’ are together, and so on. 
• Further, we will sort all the queries in every block in the increasing order of their ‘r’ values.
• Now we will compute each query making the best use of the previously computed query.    
• We need to declare some global variables such as ‘cnt’ to store the distinct elements in the current query, ‘Lptr’ and ‘Rptr’ as the left and right pointer for our current range, respectively. 
• We will be adjusting these pointers ‘Lptr’ and ‘Rptr’ to cover the current query range and updating the ‘cnt’ variable according to the inclusion or exclusion of distinct elements.
• In this way, we will store the number of distinct elements for every query and finally give the output.

Below is the implementation of the above approach.

Implementation

// Program to find the number of distinct elements.
#include <bits/stdc++.h>

using namespace std;
const int M = 1e6 + 2;

// Variables to store data.
int N, Q, l, r, cnt, Lpt, Rpt, rootn;
vector<int> Arr, ans, freq;
vector<pair<pair<int, int>, int>> pr;

// Compare function to sort the queries.
bool cmp(pair<pair<int, int>, int> p1, pair<pair<int, int>, int> p2)
{
      if (p1.first.first / rootn != p2.first.first / rootn)
            return p1.first.first < p2.first.first;
      return p1.first.second > p2.first.second;
}

// Function for expanding the left active pointer.
void expandl()
{
      while (Lpt > l)
      {
            Lpt--;
            freq[Arr[Lpt]]++;
            if (freq[Arr[Lpt]] == 1)
                  cnt++;
      }
}

// Function for expanding the right active pointer.
void expandr()
{
      while (Rpt < r)
      {
            Rpt++;
            freq[Arr[Rpt]]++;
            if (freq[Arr[Rpt]] == 1)
                  cnt++;
      }
}

// Function for compressing the left active pointer.
void compressl()
{
      while (Lpt < l)
      {
            freq[Arr[Lpt]]--;
            if (freq[Arr[Lpt]] == 0)
                  cnt--;
            Lpt++;
      }
}

// Function for compressing the right active pointer.
void compressr()
{
      while (Rpt > r)
      {
            freq[Arr[Rpt]]--;
            if (freq[Arr[Rpt]] == 0)
                  cnt--;
            Rpt--;
      }
}

// Main Function
int main()
{
      // Taking input of the data.
      cin >> N;

      // Input of the array
      Arr = vector<int>(N + 1);
      for (int i = 0; i < N; i++)
            cin >> Arr[i];

      // Number of queries.
      cin >> Q;

      /*
            Resizing the vectors according to current input
            and preparing the variables.
      */
      ans = vector<int>(Q);
      freq = vector<int>(M, 0);
      cnt = 0;
      Lpt = 0;
      Rpt = -1;

      // Square root of N.
      rootn = sqrtl(N);

      // Input of queries.
      for (int i = 0; i < Q; i++)
      {
            cin >> l >> r;
            l--, r--;
            pr.push_back({{l, r}, i});
      }

      // Sorting queries.
      sort(pr.begin(), pr.end(), cmp);

      // Computing queries.
      for (int i = 0; i < Q; i++)
      {
            // Current query range.
            l = pr[i].first.first;
            r = pr[i].first.second;

            // Adjusting Lptr and Rptr according to current range.
            if (l < Lpt)
                  expandl();
            else if (l > Lpt)
                  compressl();
            if (r < Rpt)
                  compressr();
            else if (r > Rpt)
                  expandr();

            // Storing the answer for the current query.
            ans[pr[i].second] = cnt;
      }

      // Final Output.
      for (int i = 0; i < Q; i++)
            cout << ans[i] << endl;

      return 0;
}

Input

8
1 2 3 4 4 4 7 1 
5
1 3
1 4
1 5
1 8
3 6

Output

3
4
4
5
2

Complexity Analysis

Time Complexity

O((Q + N) * √N), where ‘N’ is the size of the ‘Arr’ and ‘Q’ is the number of queries.

Explanation: In sorting the queries, the time possessed is O(Q * log(Q)). Now in further processing the queries, the right pointer ‘Rpt’ changes at most for O(N * √N) times, and the left pointer ‘Lptr’ changes at most for O(Q * √N) times. So collectively, the processing of queries takes O(N * √N + Q * √N) time. Taking ‘√N’ as common, it gives O((N + Q) * √N) of time. 

As we consider the most expensive operation of the algorithm, the time complexity of the above algorithm is O((Q + N) * √N).

Auxiliary Space

O(M), where ‘M’ is the upper limit of the array elements.

Explanation: Most space is occupied by the vector ‘freq’, which is used to store the frequency of elements of the array ‘Arr’. 

FAQs

1. What is an array?
   An array can be defined as a collection of the same type of elements. The elements are stored at contiguous memory locations and connected with the previous and next elements.
    
2. Why are we not using the brute force approach for the above problem DQUERY?
   The worst time complexity for the brute force approach in the above problem is O(N ^* Q), which is very costly and time-consuming. So we need a better approach to solve the above problem.
    
3. What is the auxiliary space for the above solution?
   The auxiliary space for the above solution is O(M), where ‘M’ is the upper limit for the array elements.
    
4. What is the time complexity for the above algorithm? 
   The time complexity for the above algorithm is the standard time complexity of Mo’s Algorithm, i.e., O((Q + N) * √N), where ‘N’ is the size of the ‘Arr’ and ‘Q’ is the number of queries.
    
5. The queries given in the above problem are which kind of queries?
   The queries discussed in the above problem are offline queries as we are not told to change the values of the array ‘Arr’. So preprocessing the queries will be sufficient, and we do not need any change. 

Key Takeaways

The above problem is an interesting competitive programming problem involving Mo’s Algorithm. Solving these types of problems is the key to enhancing your knowledge of data structures and algorithms and boosting your problem-solving skills. 

Check out this problem - Longest Subarray With Sum K 

Find more such interesting questions on our practice platform Coding Ninjas Studio if you want to learn more before jumping into practicing, head over to our library section for many such interesting blogs. Keep learning.

Happy Coding!