Dada una array de N elementos y Q consultas de la forma LR X. Para cada consulta, debe mostrar si el elemento X existe en la array entre los índices L y R (incluidos).
Prerrequisito: Ejemplos de algoritmos de Mo
:
Input : N = 5
arr = [1, 1, 5, 4, 5]
Q = 3
1 3 2
2 5 1
3 5 5
Output : No
Yes
Yes
Explanation :
For the first query, 2 does not exist between the indices 1 and 3.
For the second query, 1 exists between the indices 2 and 5.
For the third query, 5 exists between the indices 3 and 5.
Enfoque ingenuo:
el método ingenuo sería atravesar los elementos de L a R para cada consulta, buscando linealmente X. En el peor de los casos, puede haber N elementos de L a R, por lo tanto, la complejidad de tiempo en el peor de los casos para cada consulta sería estar en). Por lo tanto, para todas las consultas Q, la complejidad temporal resultaría ser O(Q*N).
Uso del método Union-Find:
este método verifica solo un elemento entre todos los valores iguales consecutivos. Si X no es igual a estos valores, entonces el algoritmo omite todos los demás elementos iguales y continúa el recorrido con el siguiente elemento diferente. Evidentemente, este algoritmo es útil solo cuando hay elementos iguales consecutivos en grandes cantidades.
Algoritmo:
- Combinar todos los elementos iguales consecutivos en un grupo.
- Mientras procesa una consulta, comience desde R. Sea index = R.
- Compare un [índice] con X. Si son iguales, imprima «Sí»
y deje de recorrer el resto del rango. De lo contrario, omita todos
los elementos consecutivos que pertenecen al grupo de a[index]. El índice
se vuelve igual a uno menos que el índice de la raíz de este grupo.
- Continúe con el paso anterior hasta encontrar X o hasta que
el índice sea menor que L.
- Si el índice se vuelve menor que L, escriba “No”.
A continuación se muestra la implementación de la idea anterior.
C++
// Program to determine if the element
// exists for different range queries
#include <bits/stdc++.h>
using namespace std;
// Structure to represent a query range
struct Query
{
int L, R, X;
};
const int maxn = 100;
int root[maxn];
// Find the root of the group containing
// the element at index x
int find(int x)
{
return x == root[x] ? x : root[x] =
find(root[x]);
}
// merge the two groups containing elements
// at indices x and y into one group
int uni(int x, int y)
{
int p = find(x), q = find(y);
if (p != q) {
root[p] = root[q];
}
}
void initialize(int a[], int n, Query q[], int m)
{
// make n subsets with every
// element as its root
for (int i = 0; i < n; i++)
root[i] = i;
// consecutive elements equal in value are
// merged into one single group
for (int i = 1; i < n; i++)
if (a[i] == a[i - 1])
uni(i, i - 1);
}
// Driver code
int main()
{
int a[] = { 1, 1, 5, 4, 5 };
int n = sizeof(a) / sizeof(a[0]);
Query q[] = { { 0, 2, 2 }, { 1, 4, 1 },
{ 2, 4, 5 } };
int m = sizeof(q) / sizeof(q[0]);
initialize(a, n, q, m);
for (int i = 0; i < m; i++)
{
int flag = 0;
int l = q[i].L, r = q[i].R, x = q[i].X;
int p = r;
while (p >= l)
{
// check if the current element in
// consideration is equal to x or not
// if it is equal, then x exists in the range
if (a[p] == x)
{
flag = 1;
break;
}
p = find(p) - 1;
}
// Print if x exists or not
if (flag != 0)
cout << x << " exists between [" << l
<< ", " << r << "] " << endl;
else
cout << x << " does not exist between ["
<< l << ", " << r << "] " << endl;
}
}
Java
// Java program to determine if the element
// exists for different range queries
import java.util.*;
class GFG
{
// Structure to represent a query range
static class Query
{
int L, R, X;
public Query(int L, int R, int X)
{
this.L = L;
this.R = R;
this.X = X;
}
};
static int maxn = 100;
static int []root = new int[maxn];
// Find the root of the group containing
// the element at index x
static int find(int x)
{
if(x == root[x])
return x;
else
return root[x] = find(root[x]);
}
// merge the two groups containing elements
// at indices x and y into one group
static void uni(int x, int y)
{
int p = find(x), q = find(y);
if (p != q)
{
root[p] = root[q];
}
}
static void initialize(int a[], int n,
Query q[], int m)
{
// make n subsets with every
// element as its root
for (int i = 0; i < n; i++)
root[i] = i;
// consecutive elements equal in value are
// merged into one single group
for (int i = 1; i < n; i++)
if (a[i] == a[i - 1])
uni(i, i - 1);
}
// Driver code
public static void main(String args[])
{
int a[] = { 1, 1, 5, 4, 5 };
int n = a.length;
Query q[] = { new Query(0, 2, 2 ),
new Query( 1, 4, 1 ),
new Query( 2, 4, 5 ) };
int m = q.length;
initialize(a, n, q, m);
for (int i = 0; i < m; i++)
{
int flag = 0;
int l = q[i].L, r = q[i].R, x = q[i].X;
int p = r;
while (p >= l)
{
// check if the current element in
// consideration is equal to x or not
// if it is equal, then x exists in the range
if (a[p] == x)
{
flag = 1;
break;
}
p = find(p) - 1;
}
// Print if x exists or not
if (flag != 0)
System.out.println(x + " exists between [" +
l + ", " + r + "] ");
else
System.out.println(x + " does not exist between [" +
l + ", " + r + "] ");
}
}
}
// This code is contributed by 29AjayKumar
Python3
# Python3 program to determine if the element
# exists for different range queries
# Structure to represent a query range
class Query:
def __init__(self, L, R, X):
self.L = L
self.R = R
self.X = X
maxn = 100
root = [0] * maxn
# Find the root of the group containing
# the element at index x
def find(x):
if x == root[x]:
return x
else:
root[x] = find(root[x])
return root[x]
# merge the two groups containing elements
# at indices x and y into one group
def uni(x, y):
p = find(x)
q = find(y)
if p != q:
root[p] = root[q]
def initialize(a, n, q, m):
# make n subsets with every
# element as its root
for i in range(n):
root[i] = i
# consecutive elements equal in value are
# merged into one single group
for i in range(1, n):
if a[i] == a[i - 1]:
uni(i, i - 1)
# Driver Code
if __name__ == "__main__":
a = [1, 1, 5, 4, 5]
n = len(a)
q = [Query(0, 2, 2),
Query(1, 4, 1),
Query(2, 4, 5)]
m = len(q)
initialize(a, n, q, m)
for i in range(m):
flag = False
l = q[i].L
r = q[i].R
x = q[i].X
p = r
while p >= l:
# check if the current element in
# consideration is equal to x or not
# if it is equal, then x exists in the range
if a[p] == x:
flag = True
break
p = find(p) - 1
# Print if x exists or not
if flag:
print("%d exists between [%d, %d]" % (x, l, r))
else:
print("%d does not exists between [%d, %d]" % (x, l, r))
# This code is contributed by
# sanjeev2552
C#
// C# program to determine if the element
// exists for different range queries
using System;
class GFG
{
// Structure to represent a query range
public class Query
{
public int L, R, X;
public Query(int L, int R, int X)
{
this.L = L;
this.R = R;
this.X = X;
}
};
static int maxn = 100;
static int []root = new int[maxn];
// Find the root of the group containing
// the element at index x
static int find(int x)
{
if(x == root[x])
return x;
else
return root[x] = find(root[x]);
}
// merge the two groups containing elements
// at indices x and y into one group
static void uni(int x, int y)
{
int p = find(x), q = find(y);
if (p != q)
{
root[p] = root[q];
}
}
static void initialize(int []a, int n,
Query []q, int m)
{
// make n subsets with every
// element as its root
for (int i = 0; i < n; i++)
root[i] = i;
// consecutive elements equal in value are
// merged into one single group
for (int i = 1; i < n; i++)
if (a[i] == a[i - 1])
uni(i, i - 1);
}
// Driver code
public static void Main(String []args)
{
int []a = { 1, 1, 5, 4, 5 };
int n = a.Length;
Query []q = {new Query(0, 2, 2),
new Query(1, 4, 1),
new Query(2, 4, 5)};
int m = q.Length;
initialize(a, n, q, m);
for (int i = 0; i < m; i++)
{
int flag = 0;
int l = q[i].L, r = q[i].R, x = q[i].X;
int p = r;
while (p >= l)
{
// check if the current element in
// consideration is equal to x or not
// if it is equal, then x exists in the range
if (a[p] == x)
{
flag = 1;
break;
}
p = find(p) - 1;
}
// Print if x exists or not
if (flag != 0)
Console.WriteLine(x + " exists between [" +
l + ", " + r + "] ");
else
Console.WriteLine(x + " does not exist between [" +
l + ", " + r + "] ");
}
}
}
// This code is contributed by PrinciRaj1992
Javascript
<script>
// Javascript program to determine if the element
// exists for different range queries
// Structure to represent a query range
class Query
{
constructor(L, R, X)
{
this.L = L;
this.R = R;
this.X = X;
}
};
let maxn = 100;
let root = new Array(maxn);
// Find the root of the group containing
// the element at index x
function find(x)
{
if(x == root[x])
return x;
else
return root[x] = find(root[x]);
}
// merge the two groups containing elements
// at indices x and y into one group
function uni(x, y)
{
let p = find(x), q = find(y);
if (p != q)
{
root[p] = root[q];
}
}
function initialize(a, n, q, m)
{
// make n subsets with every
// element as its root
for (let i = 0; i < n; i++)
root[i] = i;
// consecutive elements equal in value are
// merged into one single group
for (let i = 1; i < n; i++)
if (a[i] == a[i - 1])
uni(i, i - 1);
}
// Driver code
let a = [ 1, 1, 5, 4, 5 ];
let n = a.length;
let q = [ new Query(0, 2, 2 ),
new Query( 1, 4, 1 ),
new Query( 2, 4, 5 ) ];
let m = q.length;
initialize(a, n, q, m);
for (let i = 0; i < m; i++)
{
let flag = 0;
let l = q[i].L, r = q[i].R, x = q[i].X;
let p = r;
while (p >= l)
{
// check if the current element in
// consideration is equal to x or not
// if it is equal, then x exists in the range
if (a[p] == x)
{
flag = 1;
break;
}
p = find(p) - 1;
}
// Print if x exists or not
if (flag != 0)
document.write(x + " exists between [" +
l + ", " + r + "] " + "<br>");
else
document.write(x + " does not exist between [" +
l + ", " + r + "] " + "<br>");
}
// This code is contributed by gfgking
</script>
Producción:
2 does not exist between [0, 2] 1 exists between [1, 4] 5 exists between [2, 4]
Enfoque eficiente (utilizando el algoritmo de Mo):
el algoritmo de Mo es una de las mejores aplicaciones para la descomposición de raíces cuadradas.
Se basa en la idea básica de utilizar la respuesta a la consulta anterior para calcular la respuesta de la consulta actual. Esto es posible porque el algoritmo de Mo está construido de tal manera que si se conoce F([L, R]), entonces F([L + 1, R]), F([L – 1, R]), F([L, R + 1]) y F([L, R – 1]) se pueden calcular fácilmente, cada uno en tiempo O(F).
Al responder las consultas en el orden en que se hacen, la complejidad del tiempo no se mejora a lo que se necesita. Para reducir considerablemente la complejidad del tiempo, las consultas se dividen en bloques y luego se clasifican. El algoritmo exacto para ordenar las consultas es el siguiente:
- Indicar BLOCK_SIZE = sqrt(N)
- Todas las consultas con el mismo L/BLOCK_SIZE se colocan en el mismo bloque
- Dentro de un bloque, las consultas se ordenan en función de sus valores R
- Por lo tanto, la función de clasificación compara dos consultas, Q1 y Q2, de la siguiente manera:
Q1 debe ir antes de Q2 si:
1. L1/BLOCK_SIZE<L2/BLOCK_SIZE
2. L1/BLOCK_SIZE=L2/BLOCK_SIZE y R1<R2
Después de ordenar las consultas, el siguiente paso es calcular la respuesta a la primera consulta y, en consecuencia, responder el resto de las consultas. Para determinar si un elemento en particular existe o no, verifique la frecuencia del elemento en ese rango. Una frecuencia distinta de cero confirma la existencia del elemento en ese rango.
Para almacenar la frecuencia de los elementos, se ha utilizado el mapa STL en el siguiente código.
En el ejemplo dado, la primera consulta después de ordenar la array de consultas es {0, 2, 2}. Haga un hash de las frecuencias de los elementos en [0, 2] y luego verifique la frecuencia del elemento 2 del mapa. Dado que 2 ocurre 0 veces, imprima «No».
Mientras procesa la siguiente consulta, que es {1, 4, 1} en este caso, disminuya las frecuencias de los elementos en el rango [0, 1) e incremente las frecuencias de los elementos en el rango [3, 4]. Este paso da las frecuencias de los elementos en [1, 4] y se puede ver fácilmente en el mapa que 1 existe en este rango.
Complejidad del tiempo:
la parte de preprocesamiento, es decir, la clasificación de las consultas, requiere un tiempo de O(m Log m).
La variable de índice para R cambia la mayoría de 
las veces a lo largo de la ejecución y la de L cambia su valor la mayoría de 
las veces. Por lo tanto, procesar todas las consultas lleva + = 
tiempo.
A continuación se muestra la implementación en C++ de la idea anterior:
CPP
// CPP code to determine if the element
// exists for different range queries
#include <bits/stdc++.h>
using namespace std;
// Variable to represent block size.
// This is made global, so compare()
// of sort can use it.
int block;
// Structure to represent a query range
struct Query
{
int L, R, X;
};
// 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;
}
// Determines if the element is present for 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
int currL = 0, currR = 0;
// To store the frequencies of
// elements of the given range
map<int, int> mp;
// 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, X = q[i].X;
// Decrement frequencies of extra elements
// of previous range. For example if previous
// range is [0, 3] and current range is [2, 5],
// then the frequencies of a[0] and a[1] are decremented
while (currL < L)
{
mp[a[currL]]--;
currL++;
}
// Increment frequencies of elements of current Range
while (currL > L)
{
mp[a[currL - 1]]++;
currL--;
}
while (currR <= R)
{
mp[a[currR]]++;
currR++;
}
// Decrement frequencies of elements of previous
// range. For example when previous range is [0, 10]
// and current range is [3, 8], then frequencies of
// a[9] and a[10] are decremented
while (currR > R + 1)
{
mp[a[currR - 1]]--;
currR--;
}
// Print if X exists or not
if (mp[X] != 0)
cout << X << " exists between [" << L
<< ", " << R << "] " << endl;
else
cout << X << " does not exist between ["
<< L << ", " << R << "] " << endl;
}
}
// Driver program
int main()
{
int a[] = { 1, 1, 5, 4, 5 };
int n = sizeof(a) / sizeof(a[0]);
Query q[] = { { 0, 2, 2 }, { 1, 4, 1 }, { 2, 4, 5 } };
int m = sizeof(q) / sizeof(q[0]);
queryResults(a, n, q, m);
return 0;
}
Java
// Java Program to compute sum of ranges for
// different range queries
import java.util.*;
// Class to represent a query range
class Query{
int L;
int R;
int x;
Query(int L, int R,int x){
this.L = L;
this.R = R;
this.x=x;
}
}
class Main{
// Prints sum of all query ranges. m is number of queries
// n is size of array a[].
static void queryResults(int a[], int n, ArrayList<Query> q, int m){
// Find block size
int block = (int) Math.sqrt(n);
// Sort all queries so that queries of same blocks
// are arranged together.
Collections.sort(q, new Comparator<Query>(){
// Function used to sort all queries so that all queries
// of the same block are arranged together and within a block,
// queries are sorted in increasing order of R values.
public int compare(Query x, Query y){
// Different blocks, sort by block.
if (x.L/block != y.L/block)
return (x.L < y.L ? -1 : 1);
// Same block, sort by R value
return (x.R < y.R ? -1 : 1);
}
});
// Initialize current L, current R and current sum
int currL = 0, currR = 0;
Map<Integer,Integer> mp=new HashMap<Integer,Integer>();
// Traverse through all queries
for (int i=0; i<m; i++)
{
// L and R values of current range
int L = q.get(i).L, R = q.get(i).R, X = q.get(i).x;
// 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)
{
if(mp.containsKey(a[currL])){
mp.put(a[currL],mp.get(a[currL])-1);
}
else{
mp.put(a[currL],1);
}
//mp.put(a[currL], mp.get(a[currL] - 1));
currL++;
}
// Add Elements of current Range
while (currL > L)
{
if(mp.containsKey(a[currL-1])){
mp.put(a[currL-1],mp.get(a[currL-1])+1);
}
else{
mp.put(a[currL-1],1);
}
//mp.put(a[currL], mp.get(a[currL-1]+1));
currL--;
}
while (currR <= R)
{
if(mp.containsKey(a[currR])){
mp.put(a[currR],mp.get(a[currR])+1);
}
else{
mp.put(a[currR],1);
}
//mp.put(a[currR], mp.get(a[currR]+1));
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
while (currR > R+1)
{
if(mp.containsKey(a[currR-1])){
mp.put(a[currR-1],mp.get(a[currR-1])-1);
}
else{
mp.put(a[currR-1],1);
//mp[a[currR-1]]--;
currR--;
}
}
if (mp.containsKey(X))
System.out.println(X + " exists between [" + L +
", " + R + "] ");
else
System.out.println(X + " does not exist between [" + L +
", " + R + "] ");
// Print sum of current range
}
}
// Driver program
public static void main(String argv[]){
ArrayList<Query> q = new ArrayList<Query>();
q.add(new Query(0,2,2));
q.add(new Query(1,4,1));
q.add(new Query(2,4,5));
int a[] = {1, 1, 5, 4, 5 };
queryResults(a, a.length, q, q.size());
}
}
// This code is contributed by Aarti_Rathi
Producción:
2 does not exist between [0, 2] 1 exists between [1, 4] 5 exists between [2, 4]
Publicación traducida automáticamente
Artículo escrito por aganjali10 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA