Dada una string S de longitud N, y Q consultas del siguiente tipo:
Tipo 1: 1 i X
Actualiza el i-ésimo carácter de la string con el carácter dado, X.Tipo 2: LR
Cuenta el número de caracteres distintos en el rango dado [L, R].Restricción:
- 1<=N<=500000
- 1<=Q<20000
- |S|=N
- La string S contiene solo letras en minúsculas.
Ejemplos:
Entrada: S = “abcdbbd” Q = 6
2 3 6
1 5 z
2 1 1
1 4 a
1 7 d
2 1 7
Salida:
3
1
5
Explicación:
Para las Consultas:
1. L = 3, R = 6
Los diferentes Los caracteres son: c, b, d.
ans = 3.
2. String después de la consulta actualizada como S=”abcdzbd”.
3. L = 1, R = 1
Sólo un carácter diferente.
y así sucesivamente procesar todas las consultas.Entrada: S = “aaaa”, Q = 2
1 2 b
2 1 4
Salida:
2
Enfoque ingenuo:
Tipo de consulta 1: Reemplace el i-ésimo carácter de la string con el carácter dado.
Tipo de consulta 2: recorrer la string de L a R y contar el número de caracteres distintos.
Complejidad temporal: O(N 2 )
Enfoque eficiente: este enfoque se basa en el algoritmo de conteo de frecuencia .
La idea es usar un HashMap para mapear distintos caracteres de la string con un Ordered_set que almacena índices de todas sus ocurrencias. Se utiliza Ordered_set porque se basa en el árbol rojo-negro , por lo que la inserción y eliminación de caracteres tomará O (log N).
- Inserte todos los caracteres de la string con su índice en Hash-map
- Para consultas de tipo 1, borre la aparición del carácter en el índice i e inserte la aparición del carácter X en el índice i en Hash-map
- Para consultas de tipo 2, recorra los 26 caracteres y verifique si su ocurrencia está dentro del rango [L, R], si es así, incremente el conteo. Después de atravesar, imprima el valor de la cuenta.
A continuación se muestra la implementación del enfoque anterior:
C++
#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set \
tree<int, null_type, less<int>, \
rb_tree_tag, \
tree_order_statistics_node_update>
// Function that returns the lower-
// bound of the element in ordered_set
int lower_bound(ordered_set set1, int x)
{
// Finding the position of
// the element
int pos = set1.order_of_key(x);
// If the element is not
// present in the set
if (pos == set1.size()) {
return -1;
}
// Finding the element at
// the position
else {
int element = *(set1.find_by_order(pos));
return element;
}
}
// Utility function to add the
// position of all characters
// of string into ordered set
void insert(
unordered_map<int, ordered_set>& hMap,
string S, int N)
{
for (int i = 0; i < N; i++) {
hMap[S[i] - 'a'].insert(i);
}
}
// Utility function for update
// the character at position P
void Query1(
string& S,
unordered_map<int, ordered_set>& hMap,
int pos, char c)
{
// we delete the position of the
// previous character as new
// character is to be replaced
// at the same position.
pos--;
int previous = S[pos] - 'a';
int current = c - 'a';
S[pos] = c;
hMap[previous].erase(pos);
hMap[current].insert(pos);
}
// Utility function to determine
// number of different characters
// in given range.
void Query2(
unordered_map<int, ordered_set>& hMap,
int L, int R)
{
// Iterate over all 26 alphabets
// and check if it is in given
// range using lower bound.
int count = 0;
L--;
R--;
for (int i = 0; i < 26; i++) {
int temp = lower_bound(hMap[i], L);
if (temp <= R and temp != -1)
count++;
}
cout << count << endl;
}
// Driver code
int main()
{
string S = "abcdbbd";
int N = S.size();
unordered_map<int, ordered_set> hMap;
// Insert all characters with its
// occurrence in the hash map
insert(hMap, S, N);
// Queries for sample input
Query2(hMap, 3, 6);
Query1(S, hMap, 5, 'z');
Query2(hMap, 1, 1);
Query1(S, hMap, 4, 'a');
Query1(S, hMap, 7, 'd');
Query2(hMap, 1, 7);
return 0;
}
3 1 5
Complejidad temporal: O(Q * logN) donde Q es el número de consultas y N es el tamaño de la string.
Publicación traducida automáticamente
Artículo escrito por godaraji47 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA