Consultas por número de elementos distintos desde un índice dado hasta el último índice en una array

Dada una array ‘a[]’ de tamaño n y número de consultas q. Cada consulta se puede representar mediante un número entero m. Su tarea es imprimir el número de enteros distintos desde el índice m hasta el n, es decir, hasta el último elemento de la array. 
Ejemplos: 
 

Entrada: arr[] = {1, 2, 3, 1, 2, 3, 4, 5}, q[] = {1, 4, 6, 8} 
Salida: 5 5 3 1 
En consulta 1, número de distintos enteros 
en a[0…7] es 5 (1, 2, 3, 4, 5) 
En la consulta 2, el número de enteros distintos 
en a[3…7] es 5 (1, 2, 3, 4, 5) 
En consulta 3, el número de enteros distintos 
en a[5…7] es 3 (3, 4, 5) 
En la consulta 4, el número de enteros distintos 
en a[7…7] es 1 (5) 
 

Acercarse: 
 

• Realice una verificación de array [] que verificará si el elemento actual se visitó anteriormente o no. Si ya lo visitó, márquelo como 1 , de lo contrario , 0 .
• Tome una array idx [] que almacenará la cantidad de elementos distintos desde el índice actual hasta el último índice.
• Bucle desde el último, si el elemento actual no ha sido visitado, marque su verificación como 1 , almacene el contador actual en idx e increméntelo; de lo contrario, simplemente almacene el contador actual en idx .

A continuación se muestra la implementación del enfoque anterior: 
 

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
#define MAX 100001
 
// Function to perform queries to find
// number of distinct elements from
// a given index till last index in an array
void find_distinct(int a[], int n, int q, int queries[])
{
    int check[MAX] = { 0 };
    int idx[MAX];
    int cnt = 1;
    for (int i = n - 1; i >= 0; i--) {
        // Check if current element
        // already visited or not
        if (check[a[i]] == 0) {
 
            // If not visited store current counter
            // and increment it and mark check as 1
            idx[i] = cnt;
            check[a[i]] = 1;
            cnt++;
        }
        else {
 
            // Otherwise if visited simply
            // store current counter
            idx[i] = cnt - 1;
        }
    }
 
    // Perform queries
    for (int i = 0; i < q; i++) {
        int m = queries[i];
        cout << idx[m] << " ";
    }
}
 
// Driver code
int main()
{
    int a[] = { 1, 2, 3, 1, 2, 3, 4, 5 };
    int n = sizeof(a) / sizeof(int);
    int queries[] = { 0, 3, 5, 7 };
    int q = sizeof(queries) / sizeof(int);
    find_distinct(a, n, q, queries);
 
    return 0;
}

// Java implementation of the approach
import java.util.*;
 
class GFG
{
     
static int MAX =100001;
 
// Function to perform queries to find
// number of distinct elements from
// a given index till last index in an array
static void find_distinct(int a[], int n, int q, int queries[])
{
    int []check = new int[MAX];
    int []idx = new int[MAX];
    int cnt = 1;
    for (int i = n - 1; i >= 0; i--)
    {
        // Check if current element
        // already visited or not
        if (check[a[i]] == 0)
        {
 
            // If not visited store current counter
            // and increment it and mark check as 1
            idx[i] = cnt;
            check[a[i]] = 1;
            cnt++;
        }
        else
        {
 
            // Otherwise if visited simply
            // store current counter
            idx[i] = cnt - 1;
        }
    }
 
    // Perform queries
    for (int i = 0; i < q; i++)
    {
            int m = queries[i];
            System.out.print(idx[m] + " ");
    }
}
 
// Driver code
public static void main(String[] args)
{
    int a[] = { 1, 2, 3, 1, 2, 3, 4, 5 };
    int n = a.length;
    int queries[] = { 0, 3, 5, 7 };
    int q = queries.length;
    find_distinct(a, n, q, queries);
}
}
 
// This code is contributed by Rajput-Ji

# Python implementation of the approach
MAX = 100001;
 
# Function to perform queries to find
# number of distinct elements from
# a given index till last index in an array
def find_distinct(a, n, q, queries):
    check = [0] * MAX;
    idx = [0] * MAX;
    cnt = 1;
    for i in range(n - 1, -1, -1):
         
        # Check if current element
        # already visited or not
        if (check[a[i]] == 0):
 
            # If not visited store current counter
            # and increment it and mark check as 1
            idx[i] = cnt;
            check[a[i]] = 1;
            cnt += 1;
        else:
 
            # Otherwise if visited simply
            # store current counter
            idx[i] = cnt - 1;
 
    # Perform queries
    for i in range(0, q):
        m = queries[i];
        print(idx[m], end = " ");
 
# Driver code
a = [ 1, 2, 3, 1, 2, 3, 4, 5 ];
n = len(a);
queries = [ 0, 3, 5, 7 ];
q = len(queries);
find_distinct(a, n, q, queries);
 
# This code is contributed by 29AjayKumar

// C# implementation of the approach
using System;
     
class GFG
{
     
static int MAX =100001;
 
// Function to perform queries to find
// number of distinct elements from
// a given index till last index in an array
static void find_distinct(int []a, int n, int q, int []queries)
{
    int []check = new int[MAX];
    int []idx = new int[MAX];
    int cnt = 1;
    for (int i = n - 1; i >= 0; i--)
    {
        // Check if current element
        // already visited or not
        if (check[a[i]] == 0)
        {
 
            // If not visited store current counter
            // and increment it and mark check as 1
            idx[i] = cnt;
            check[a[i]] = 1;
            cnt++;
        }
        else
        {
 
            // Otherwise if visited simply
            // store current counter
            idx[i] = cnt - 1;
        }
    }
 
    // Perform queries
    for (int i = 0; i < q; i++)
    {
            int m = queries[i];
            Console.Write(idx[m] + " ");
    }
}
 
// Driver code
public static void Main(String[] args)
{
    int []a = { 1, 2, 3, 1, 2, 3, 4, 5 };
    int n = a.Length;
    int []queries = { 0, 3, 5, 7 };
    int q = queries.Length;
    find_distinct(a, n, q, queries);
}
}
 
/* This code is contributed by PrinciRaj1992 */

<script>
 
 
// JavaScript implementation of the approach
 
// Function to perform queries to find
// number of distinct elements from
// a given index till last index in an array
function find_distinct(a, n, q, queries)
{
    let MAX =100001;
    let check = new Array(MAX).fill(0);
    let idx = new Array(MAX).fill(0);
    let cnt = 1;
     
    let i=n-1;
     
    while (i>=0) {
     // Check if current element
        // already visited or not
        if (check[a[i]] == 0)
        {
 
            // If not visited store current counter
            // and increment it and mark check as 1
            idx[i] = cnt;
            check[a[i]] = 1;
            cnt++;
        }
        else
        {
 
            // Otherwise if visited simply
            // store current counter
            idx[i] = cnt - 1;
        }
    i--;
    }
     
 
    // Perform queries
    for (let i = 0; i < q; i++)
    {
            let m = queries[i];
            document.write(idx[m] + " ");
    }
     
}
 
// Driver code
 
let a = [1, 2, 3, 1, 2, 3, 4, 5 ];
let n = a.length;
let queries = [0, 3, 5, 7];
let q = queries.length;
find_distinct(a, n, q, queries);
 
 
 
</script>

5 5 3 1

Complejidad de Tiempo: O(MAX + N)
Espacio Auxiliar: O(MAX)