Dada una array arr[] que consiste en números enteros y consultas Q de la forma (L, R) , la tarea es verificar si algún elemento que no se repite está presente dentro de los índices [L, R] (indexación basada en 1) o no. Si hay al menos un elemento que no se repite, imprima «Sí» . De lo contrario, escriba “No” .
Ejemplos:
Entrada: arr[] = {1, 2, 1, 2, 3, 4}, Consultas[][] = {{1, 4}, {1, 5}}
Salida: No Sí
Explicación:
Para la primera consulta, el subarreglo es {1, 2, 1, 2}, podemos ver que ambos números tienen una frecuencia de 2. Por lo tanto, la respuesta es No.
Para la segunda consulta, el subarreglo es {1, 2, 1, 2, 3}, podemos ver que 3 tiene frecuencia 1 por lo que la respuesta es Sí.Entrada: array[] = {1, 2, 3, 4, 5}, Consultas[][] = {{1, 4}}
Salida: Sí
Explicación: El subarreglo es {1, 2, 3, 4}, tiene todos los elementos como frecuencia 1 por lo que la respuesta es Sí.
Enfoque ingenuo:
el enfoque más simple para resolver el problema es iterar sobre un subarreglo dado para cada consulta y mantener un mapa para almacenar la frecuencia de cada elemento. Iterar sobre el mapa y verificar si hay un elemento de frecuencia 1 o no.
Complejidad de Tiempo: O(Q * N)
Complejidad de Espacio Auxiliar: O(N)
Enfoque eficiente: la observación clave para la solución es que, para que el elemento tenga la frecuencia 1 en la array dada, la aparición anterior de este número en la array es estrictamente menor que la consulta l y la próxima aparición del elemento es estrictamente mayor que r de alguna consulta. Usa esta observación para encontrar el orden. A continuación se muestran los pasos que utilizan el enfoque Merge Sort Tree para resolver el problema dado:
- Almacene la ocurrencia anterior y la ocurrencia siguiente de cada i-ésimo elemento en la array como par .
- Cree el árbol de clasificación de combinación y combine los Nodes en ellos de acuerdo con la ocurrencia anterior. La función de fusión se utiliza para fusionar los rangos.
- En cada Node del árbol de ordenación por combinación, mantenga el prefijo máximo en la siguiente ocurrencia porque necesitamos la ocurrencia anterior más pequeña posible y la siguiente ocurrencia tan grande de algún elemento.
- Para responder a la consulta, necesitamos un Node con una ocurrencia anterior estrictamente menor que l.
- Para el elemento en el árbol de ordenación de combinación con la ocurrencia anterior menor que l, encuentre la próxima ocurrencia máxima y verifique si la próxima ocurrencia es mayor que r de la consulta, entonces hay un elemento presente en el subarreglo con frecuencia 1.
A continuación se muestra la implementación del enfoque anterior:
CPP
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9 + 9;
const int N = 1e5 + 5;
// Merge sort of pair type for storing
// prev and next occurrences of element
vector<vector<pair<int, int> > > segtree(4 * N);
// Stores the occurrences
vector<pair<int, int> > occurrences(N);
// Finds occurrences
vector<set<int> > pos(N);
int n;
// Function to build merge sort tree
void build(int node = 0, int l = 0,
int r = n - 1)
{
// For leaf node, push the prev &
// next occurrence of the lth node
if (l == r) {
segtree[node].push_back(occurrences[l]);
return;
}
int mid = (l + r) / 2;
// Left recursion call
build(2 * node + 1, l, mid);
// Right recursion call
build(2 * node + 2, mid + 1, r);
// Merging the left child and right child
// according to the prev occurrence
merge(segtree[2 * node + 1].begin(),
segtree[2 * node + 1].end(),
segtree[2 * node + 2].begin(),
segtree[2 * node + 2].end(),
back_inserter(segtree[node]));
// Update the next occurrence
// with prefix maximum
int mx = 0;
for (auto& i : segtree[node]) {
// Update the maximum
// next occurrence
mx = max(mx, i.second);
// Update the next occurrence
// with prefix max
i.second = mx;
}
}
// Function to check whether an
// element is present from x to y
// with frequency 1
bool query(int x, int y, int node = 0,
int l = 0, int r = n - 1)
{
// No overlap condition
if (l > y || r < x || x > y)
return false;
// Complete overlap condition
if (x <= l && r <= y) {
// Find the first node with
// prev occurrence >= x
auto it = lower_bound(segtree[node].begin(),
segtree[node].end(),
make_pair(x, -1));
// No element in this range with
// previous occurrence less than x
if (it == segtree[node].begin())
return false;
else {
it--;
// Check if the max next
// occurrence is greater
// than y or not
if (it->second > y)
return true;
else
return false;
}
}
int mid = (l + r) / 2;
bool a = query(x, y, 2 * node + 1, l, mid);
bool b = query(x, y, 2 * node + 2, mid + 1, r);
// Return if any of the
// children returned true
return (a | b);
}
// Function do preprocessing that
// is finding the next and previous
// occurrences
void preprocess(int arr[])
{
// Store the position of
// every element
for (int i = 0; i < n; i++) {
pos[arr[i]].insert(i);
}
for (int i = 0; i < n; i++) {
// Find the previous
// and next occurrences
auto it = pos[arr[i]].find(i);
if (it == pos[arr[i]].begin())
occurrences[i].first = -INF;
else
occurrences[i].first = *prev(it);
// Check if there is no next occurrence
if (next(it) == pos[arr[i]].end())
occurrences[i].second = INF;
else
occurrences[i].second = *next(it);
}
// Building the merge sort tree
build();
}
// Function to find whether there is a
// number in the subarray with 1 frequency
void answerQueries(int arr[],
vector<pair<int, int> >& queries)
{
preprocess(arr);
// Answering the queries
for (int i = 0; i < queries.size(); i++) {
int l = queries[i].first - 1;
int r = queries[i].second - 1;
bool there = query(l, r);
if (there == true)
cout << "Yes\n";
else
cout << "No\n";
}
}
// Driver Code
int main()
{
int arr[] = { 1, 2, 1, 2, 3, 4 };
n = sizeof(arr) / sizeof(arr[0]);
vector<pair<int, int> > queries = { { 1, 4 }, { 1, 5 } };
answerQueries(arr, queries);
}
No Yes
Complejidad de tiempo: O(N*log(N) + Q*log 2 (N))
Espacio auxiliar: O(N*log(N))
Tema relacionado: Árbol de segmentos
Publicación traducida automáticamente
Artículo escrito por insiderpants y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA