Запросы диапазона строк для подсчета количества отдельных символов с обновлениями

Опубликовано: 1 Января, 2022

Дана строка S длины N и Q запросов следующего типа:

Type 1: 1 i X
Update the i-th character of the string with the given character, X.
Type 2: L R
Count number of distinct characters in the given range [L, R].
Constraint:
1<=N<=500000
1<=Q<20000
|S|=N
String S contains only lowercase alphabets.

Примеры:

Input: S = “abcdbbd” Q = 6
2 3 6
1 5 z
2 1 1
1 4 a
1 7 d
2 1 7
Output:
3
1
5
Explanation:
For the Queries:
1. L = 3, R = 6
The different characters are:c, b, d.
ans = 3.
2. String after query updated as S=”abcdzbd”.
3. L = 1, R = 1
Only one different character.
and so on process all queries.
Input: S = “aaaaa”, Q = 2
1 2 b
2 1 4
Output:
2

Наивный подход:

Тип запроса 1: заменить i-й символ строки заданным символом.
Тип запроса 2: перейдите по строке от L к R и подсчитайте количество различных символов.

Временная сложность: O (N ² )

Эффективный подход: этот подход основан на алгоритме подсчета частот.
Идея состоит в том, чтобы использовать HashMap для сопоставления отдельных символов строки с Ordered_set, в котором хранятся индексы всех его вхождений. Ordered_set используется, потому что он основан на красно-черном дереве, поэтому для вставки и удаления символа потребуется O (журнал N).

Вставить все символы строки с ее индексом в Hash-карту
Для запроса типа 1 удалите вхождение символа в индексе i и вставьте вхождение символа X в индекс i в Hash-map
Для запроса типа 2 просмотрите все 26 символов и проверьте, находится ли его вхождение в диапазоне [L, R], если да, то увеличьте счетчик. После обхода выведите значение счетчика.

Ниже представлена реализация описанного выше подхода:

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

Сложность по времени: O (Q * logN), где Q - количество запросов, а N - размер строки.

Вниманию читателя! Не прекращайте учиться сейчас. Освойте все важные концепции DSA с помощью самостоятельного курса DSA по доступной для студентов цене и будьте готовы к работе в отрасли. Получите все важные математические концепции для соревновательного программирования с курсом Essential Maths for CP по доступной для студентов цене.

Если вы хотите посещать живые занятия с отраслевыми экспертами, пожалуйста, обращайтесь к Geeks Classes Live и Geeks Classes Live USA.

Олимпиады по программированию Алгоритмы

Запросы диапазона строк для подсчета количества отдельных символов с обновлениями

C ++

РЕКОМЕНДУЕМЫЕ СТАТЬИ