Elementos distintos en subarreglo usando el Algoritmo de Mo

Dada una array ‘a[]’ de tamaño n y número de consultas q. Cada consulta se puede representar mediante dos números enteros l y r. Su tarea es imprimir el número de enteros distintos en el subarreglo l a r. Dado a[i] <=  Ejemplos:

Input : a[] = {1, 1, 2, 1, 2, 3}
        q = 3
        0 4
        1 3
        2 5
Output : 2
         2
         3
In query 1, number of distinct integers
in a[0...4] is 2 (1, 2)
In query 2, number of distinct integers 
in a[1..3] is 2 (1, 2)
In query 3, number of distinct integers 
in a[2..5] is 3 (1, 2, 3)

Input : a[] = {7, 3, 5, 9, 7, 6, 4, 3, 2}
        q = 4
        1 5
        0 4
        0 7
        1 8
output : 5
         4
         6
         7

Sea a[0…n-1] una array de entrada y q[0..m-1] una array de consultas. Acercarse :

1. Ordene todas las consultas de manera que  se junten las consultas con valores L de 0 a , luego todas las consultas de  a  , y así sucesivamente. Todas las consultas dentro de un bloque se clasifican en orden creciente de valores R.
2. Inicialice una array freq[] de tamaño  con 0 . La array freq[] lleva la cuenta de las frecuencias de todos los elementos que se encuentran en un rango determinado.
3. Procese todas las consultas una por una de manera que cada consulta use una cantidad de elementos diferentes y una array de frecuencia calculada en la consulta anterior y almacene el resultado en una estructura.
   • Sea ‘curr_Diff_element’ el número de elementos diferentes de la consulta anterior.
   • Eliminar elementos adicionales de la consulta anterior. Por ejemplo, si la consulta anterior es [0, 8] y la consulta actual es [3, 9], elimine a [0], a [1] y a [2]
   • Agregar nuevos elementos de la consulta actual. En el mismo ejemplo anterior, agregue a[9].
4. Ordene las consultas en el mismo orden en que se proporcionaron anteriormente e imprima sus resultados almacenados

Agregando elements()

• Aumente la frecuencia del elemento que se agregará (freq[a[i]]) en 1.
• Si la frecuencia del elemento a[i] es 1, aumente curr_diff_element en 1 ya que se ha agregado 1 nuevo elemento en el rango.

Eliminando elements() 

• Disminuya la frecuencia del elemento a eliminar (a[i]) en 1.
• si la frecuencia de un elemento a[i] es 0. Simplemente disminuya curr_diff_element en 1 ya que 1 elemento se ha eliminado por completo del rango.

Nota: En este algoritmo, en el paso 2, la variable de índice para R cambia como máximo O(n *  ) veces a lo largo de la ejecución y lo mismo para L cambia su valor como máximo O(m *  ) veces. Todos estos límites son posibles solo porque las consultas ordenadas primero en bloques de  tamaño. La parte de preprocesamiento toma un tiempo O(m Log m). El procesamiento de todas las consultas requiere O(n *  ) + O(m *  ) = O((m+n) * ) tiempo. A continuación se muestra la implementación del enfoque anterior: 

// Program to compute no. of different elements
// of ranges for different range queries
#include <bits/stdc++.h>
using namespace std;
 
// Used in frequency array (maximum value of an
// array element).
const int MAX = 1000000;
 
// Variable to represent block size. This is made
// global so compare() of sort can use it.
int block;
 
// Structure to represent a query range and to store
// index and result of a particular query range
struct Query {
    int L, R, index, result;
};
 
// Function used to sort all queries so that all queries
// of same block are arranged together and within a block,
// queries are sorted in increasing order of R values.
bool compare(Query x, Query y)
{
    // Different blocks, sort by block.
    if (x.L / block != y.L / block)
        return x.L / block < y.L / block;
 
    // Same block, sort by R value
    return x.R < y.R;
}
 
// Function used to sort all queries in order of their
// index value so that results of queries can be printed
// in same order as of input
bool compare1(Query x, Query y)
{
    return x.index < y.index;
}
 
// calculate distinct elements of all query ranges.
// m is number of queries n is size of array a[].
void queryResults(int a[], int n, Query q[], int m)
{
    // Find block size
    block = (int)sqrt(n);
 
    // Sort all queries so that queries of same
    // blocks are arranged together.
    sort(q, q + m, compare);
 
    // Initialize current L, current R and current
    // different elements
    int currL = 0, currR = 0;
    int curr_Diff_elements = 0;
 
    // Initialize frequency array with 0
    int freq[MAX] = { 0 };
 
    // Traverse through all queries
    for (int i = 0; i < m; i++) {
         
        // L and R values of current range
        int L = q[i].L, R = q[i].R;
 
        // Remove extra elements of previous range.
        // For example if previous range is [0, 3]
        // and current range is [2, 5], then a[0]
        // and a[1] are subtracted
        while (currL < L) {
             
            // element a[currL] is removed
            freq[a[currL]]--;
            if (freq[a[currL]] == 0)
                curr_Diff_elements--;
             
            currL++;
        }
 
        // Add Elements of current Range
        // Note:- during addition of the left
        // side elements we have to add currL-1
        // because currL is already in range
        while (currL > L) {
            freq[a[currL - 1]]++;
 
            // include a element if it occurs first time
            if (freq[a[currL - 1]] == 1)
                curr_Diff_elements++;
             
            currL--;
        }
        while (currR <= R) {
            freq[a[currR]]++;
 
            // include a element if it occurs first time
            if (freq[a[currR]] == 1)
                curr_Diff_elements++;
             
            currR++;
        }
 
        // Remove elements of previous range. For example
        // when previous range is [0, 10] and current range
        // is [3, 8], then a[9] and a[10] are subtracted
        // Note:- Basically for a previous query L to R
        // currL is L and currR is R+1. So during removal
        // of currR remove currR-1 because currR was
        // never included
        while (currR > R + 1) {
 
            // element a[currL] is removed
            freq[a[currR - 1]]--;
 
            // if occurrence of a number is reduced
            // to zero remove it from list of
            // different elements
            if (freq[a[currR - 1]] == 0)
                curr_Diff_elements--;
             
            currR--;
        }
        q[i].result = curr_Diff_elements;
    }
}
 
// print the result of all range queries in
// initial order of queries
void printResults(Query q[], int m)
{
    sort(q, q + m, compare1);
    for (int i = 0; i < m; i++) {
        cout << "Number of different elements" <<
               " in range " << q[i].L << " to "
             << q[i].R << " are " << q[i].result << endl;
    }
}
 
// Driver program
int main()
{
    int a[] = { 1, 1, 2, 1, 3, 4, 5, 2, 8 };
    int n = sizeof(a) / sizeof(a[0]);
    Query q[] = { { 0, 4, 0, 0 }, { 1, 3, 1, 0 },
                  { 2, 4, 2, 0 } };
    int m = sizeof(q) / sizeof(q[0]);
    queryResults(a, n, q, m);
    printResults(q, m);
    return 0;
}

//Java program to compute no. of different elements
// of ranges for different range queries
 
import java.io.*;
import java.util.*;
 
class GFG {
     
    // Class to represent a query range and to store
    // index and result of a particular query range
    public static class Query{
        int L, R, index, result;
        Query(int l, int r, int i, int res){
            this.L = l;
            this.R = r;
            this.index = i;
            this.result = res;
        }
    }
     
    // Used in frequency array (maximum value of an
    // array element).
   public static  int MAX = 1000000;
       
    // Variable to represent block size. This is made
    // global so compare() of sort can use it.
    public static int block;
     
    // calculate distinct elements of all query ranges.
    // m is number of queries n is size of array a[].
    public static void queryResults(int a[], int n, Query q[], int m)
    {
        // Find block size
        block = (int)Math.sqrt(n);
       
        // Sort all queries so that all queries
        // of same block are arranged together and within a block,
        // queries are sorted in increasing order of R values.
        Arrays.sort(q, new Comparator<Query>() {
            public int compare(Query x, Query y) {
                // Different blocks, sort by block.
                if (x.L / block != y.L / block)
                    return x.L / block < y.L / block?1:-1;
               
                // Same block, sort by R value
                return x.R < y.R?1:-1;
            }
        });
       
        // Initialize current L, current R and current
        // different elements
        int currL = 0, currR = 0;
        int curr_Diff_elements = 0;
       
        // Initialize frequency array with 0
        int freq[] = new int[MAX];
        Arrays.fill(freq,0);
       
        // Traverse through all queries
        for (int i = 0; i < m; i++) {
               
            // L and R values of current range
            int L = q[i].L, R = q[i].R;
       
            // Remove extra elements of previous range.
            // For example if previous range is [0, 3]
            // and current range is [2, 5], then a[0]
            // and a[1] are subtracted
            while (currL < L) {
                   
                // element a[currL] is removed
                freq[a[currL]]--;
                if (freq[a[currL]] == 0) {
                    curr_Diff_elements--;
                }
                currL++;
            }
       
            // Add Elements of current Range
            // Note:- during addition of the left
            // side elements we have to add currL-1
            // because currL is already in range
            while (currL > L) {
                freq[a[currL - 1]]++;
       
                // include a element if it occurs first time
                if (freq[a[currL - 1]] == 1) {
                    curr_Diff_elements++;
                }
                currL--;
            }
            while (currR <= R) {
                freq[a[currR]]++;
       
                // include a element if it occurs first time
                if (freq[a[currR]] == 1){
                    curr_Diff_elements++;
                }
                currR++;
            }
       
            // Remove elements of previous range. For example
            // when previous range is [0, 10] and current range
            // is [3, 8], then a[9] and a[10] are subtracted
            // Note:- Basically for a previous query L to R
            // currL is L and currR is R+1. So during removal
            // of currR remove currR-1 because currR was
            // never included
            while (currR > R + 1) {
       
                // element a[currL] is removed
                freq[a[currR - 1]]--;
       
                // if occurrence of a number is reduced
                // to zero remove it from list of
                // different elements
                if (freq[a[currR - 1]] == 0){
                    curr_Diff_elements--;
                }
                currR--;
            }
            q[i].result = curr_Diff_elements;
        }
    }
     
    // print the result of all range queries in
    // initial order of queries
    public static void printResults(Query q[], int m)
    {
        // FSort all queries in order of their
        // index value so that results of queries can be printed
        // in same order as of input
        Arrays.sort(q, new Comparator<Query>() {
            public int compare(Query x, Query y) {
                return (x.index < y.index)?-1:1;
            }
        });
         
         
        for (int i = 0; i < m; i++) {
            System.out.println("Number of different elements in range " + q[i].L + " to " + q[i].R + " are " + q[i].result);
        }
    }
     
    //Driver Code
    public static void main (String[] args) {
        int a[] = { 1, 1, 2, 1, 3, 4, 5, 2, 8 };
        int n = a.length;
        Query q[] = new Query[3];
        q[0]=new Query(0,4,0,0);
        q[1] = new Query(1, 3, 1, 0);
        q[2] = new Query( 2, 4, 2, 0);
        int m = q.length;
        queryResults(a, n, q, m);
        printResults(q, m);
    }
}
//This code is contributed by shruti456rawal

Number of different elements in range 0 to 4 are 3
Number of different elements in range 1 to 3 are 2
Number of different elements in range 2 to 4 are 3