Dada una array arr[] de tamaño N y Q consultas de la forma [L, R], la tarea es encontrar el número de valores distintos en esta array en el rango dado. Ejemplos:
Entrada: arr[] = {4, 1, 9, 1, 3, 3}, Q = {{1, 3}, {1, 5}} Salida: 3 4 Explicación: Para consulta {1, 3}, elementos son {4, 1, 9}. Por lo tanto, cuenta de elementos distintos = 3 Para la consulta {1, 5}, los elementos son {4, 1, 9, 1, 3}. Por lo tanto, cuenta de elementos distintos = 4 Entrada: arr[] = {4, 2, 1, 1, 4}, Q = {{2, 4}, {3, 5}} Salida: 3 2
Enfoque ingenuo: una solución simple es que para cada consulta, itere la array de L a R e inserte elementos en un conjunto. Finalmente, el Tamaño del conjunto da el número de elementos distintos de L a R. Complejidad de tiempo: O(Q * N) Enfoque eficiente: La idea es usar Merge Sort Tree para resolver este problema.
- Almacenaremos la próxima aparición del elemento en una array temporal.
- Luego, para cada consulta de L a R, encontraremos la cantidad de elementos en la array temporal cuyos valores son mayores que R en el rango de L a R.
Paso 1: tome una array next_right, donde next_right[i] contiene el siguiente índice derecho del número i en la array a. Inicialice esta array como N (longitud de la array). Paso 2: Cree un árbol de clasificación de combinación a partir de la array next_right y realice consultas. Las consultas para calcular el número de elementos distintos de L a R equivalen a encontrar el número de elementos de L a R que son mayores que R.
Construcción de Merge Sort Tree a partir de una array dada
- Empezamos con un segmento arr[0 . . . n-1].
- Cada vez que dividimos el segmento actual en dos mitades si aún no se ha convertido en un segmento de longitud 1. Luego llamamos al mismo procedimiento en ambas mitades, y para cada uno de esos segmentos, almacenamos la array ordenada en cada segmento como en la ordenación por fusión.
- Además, el árbol será un árbol binario completo porque siempre dividimos los segmentos en dos mitades en cada nivel.
- Dado que el árbol construido siempre es un árbol binario completo con n hojas, habrá N-1 Nodes internos. Entonces, el número total de Nodes será 2*N – 1.
Aquí hay un ejemplo. Digamos que 1 5 2 6 9 4 7 1 sea una array.
|1 1 2 4 5 6 7 9| |1 2 5 6|1 4 7 9| |1 5|2 6|4 9|1 7| |1|5|2|6|9|4|7|1|
Construcción de la array next_right
- Almacenamos la siguiente ocurrencia correcta de cada elemento.
- Si el elemento tiene la última aparición, almacenamos ‘N’ (Longitud de la array) Ejemplo:
arr = [2, 3, 2, 3, 5, 6]; next_right = [2, 3, 6, 6, 6, 6]
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation to find // count of distinct elements // in a range L to R for Q queries #include <bits/stdc++.h> using namespace std; // Function to merge the right // and the left tree void merge(vector<int> tree[], int treeNode) { int len1 = tree[2 * treeNode].size(); int len2 = tree[2 * treeNode + 1].size(); int index1 = 0, index2 = 0; // Fill this array in such a // way such that values // remain sorted similar to mergesort while (index1 < len1 && index2 < len2) { // If the element on the left part // is greater than the right part if (tree[2 * treeNode][index1] > tree[2 * treeNode + 1][index2]) { tree[treeNode].push_back( tree[2 * treeNode + 1][index2] ); index2++; } else { tree[treeNode].push_back( tree[2 * treeNode][index1] ); index1++; } } // Insert the leftover elements // from the left part while (index1 < len1) { tree[treeNode].push_back( tree[2 * treeNode][index1] ); index1++; } // Insert the leftover elements // from the right part while (index2 < len2) { tree[treeNode].push_back( tree[2 * treeNode + 1][index2] ); index2++; } return; } // Recursive function to build // segment tree by merging the // sorted segments in sorted way void build(vector<int> tree[], int* arr, int start, int end, int treeNode) { // Base case if (start == end) { tree[treeNode].push_back( arr[start]); return; } int mid = (start + end) / 2; // Building the left tree build(tree, arr, start, mid, 2 * treeNode); // Building the right tree build(tree, arr, mid + 1, end, 2 * treeNode + 1); // Merges the right tree // and left tree merge(tree, treeNode); return; } // Function similar to query() method // as in segment tree int query(vector<int> tree[], int treeNode, int start, int end, int left, int right) { // Current segment is out of the range if (start > right || end < left) { return 0; } // Current segment completely // lies inside the range if (start >= left && end <= right) { // as the elements are in sorted order // so number of elements greater than R // can be find using binary // search or upper_bound return tree[treeNode].end() - upper_bound(tree[treeNode].begin(), tree[treeNode].end(), right); } int mid = (start + end) / 2; // Query on the left tree int op1 = query(tree, 2 * treeNode, start, mid, left, right); // Query on the Right tree int op2 = query(tree, 2 * treeNode + 1, mid + 1, end, left, right); return op1 + op2; } // Driver Code int main() { int n = 5; int arr[] = { 1, 2, 1, 4, 2 }; int next_right[n]; // Initialising the tree vector<int> tree[4 * n]; unordered_map<int, int> ump; // Construction of next_right // array to store the // next index of occurrence // of elements for (int i = n - 1; i >= 0; i--) { if (ump[arr[i]] == 0) { next_right[i] = n; ump[arr[i]] = i; } else { next_right[i] = ump[arr[i]]; ump[arr[i]] = i; } } // building the mergesort tree // by using next_right array build(tree, next_right, 0, n - 1, 1); int ans; // Queries one based indexing // Time complexity of each // query is log(N) // first query int left1 = 0; int right1 = 2; ans = query(tree, 1, 0, n - 1, left1, right1); cout << ans << endl; // Second Query int left2 = 1; int right2 = 4; ans = query(tree, 1, 0, n - 1, left2, right2); cout << ans << endl; }
2 3
Complejidad del tiempo: O(Q*log N)
Publicación traducida automáticamente
Artículo escrito por piyushbhutani y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA