Dada una string S de longitud N, y M consultas del siguiente tipo:
Tipo 1: 1 L x,
indica actualizar el índice Lth de la string S por el carácter ‘x’.
Tipo 2: 2 LR str
Encuentre el número de subconjuntos en el rango L a R
que es igual a la string str módulo 1000000007.
Restricciones:
|S| <= 100000,
M <= 100000,
1 <= L, R <= |S|,
|str| <= 26,
todos los caracteres en str son únicos,
S y str consisten en letras latinas en minúsculas.
Ejemplos:
Entrada: N = 16, M = 3, S = tipo «geeekkksgskeegks»
= 2: L = 1, R = 7, str = tipo «gek»
= 1: índice = 2, carácter = tipo ‘x’
= 2: L = 1, R = 7, str = “gek”
Salida: 9 6 4
consulta2: número de subconjuntos en la string S i rango [1…7] que es igual a gek es 9.
consulta1: la string S se cambia a gxeekkksgskeegks después del segundo consulta.
consulta2: el número de subconjuntos en la string S i rango [1…7] que es igual a gek es 6.
Enfoque ingenuo:
tipo de consulta 1: calcularemos la frecuencia de cada carácter de la string de consulta en el rango [L…R] y luego multiplicaremos todas las frecuencias calculadas para obtener el resultado deseado.
Consulta tipo 2: Reemplazaremos el i-ésimo carácter de la string con el carácter dado.
Complejidad de tiempo : 0(m*n)
Enfoque eficiente:
- Usando Segment Tree podemos realizar ambas operaciones en tiempo log(n). Cada Node del árbol de segmentos contendrá la frecuencia de los caracteres en el rango [L..R].
- La construcción de la función tarda n*log(n) en crear un árbol de segmentos con cada Node que contiene la frecuencia de los caracteres de algún segmento de la string.
- La función get devuelve un vector que contiene la frecuencia de todos los caracteres. La multiplicación de todas las frecuencias de la string de consulta dada módulo 1e9+7 da el resultado deseado.
- La actualización de la función disminuye la frecuencia de los caracteres colocados anteriormente y aumenta en uno la frecuencia de los nuevos caracteres presentes en los Nodes del árbol de segmentos.
- La función add_two_result agrega dos vectores y devuelve su resultado.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include<bits/stdc++.h>
using namespace std;
#define N 400005
#define mod 1000000007
vector <int> seg_tree[N];
string str;
// A recursive function that constructs
// Segment Tree for given string
void build(int pos, int st, int en)
{
if (st == en)
{
// Increment the frequency of character
// by one if st is equal to en
seg_tree[pos][str[st - 1] - 'a']++;
return ;
}
int mid = st + en >> 1;
// Build the segment tree for range st to mid
build(2 * pos, st, mid);
// Build the segment tree for range mid+1 to en
build(2 * pos + 1, mid + 1, en);
// It stores addition of frequency of
// characters of both of its child after
// segment tree is build
for (int i = 0; i < 26; i++)
seg_tree[pos][i] = seg_tree[2 * pos + 1][i]
+ seg_tree[2 * pos][i];
}
// A utility function for
// addition of two vectors
vector <int> add_two_result(vector <int> v1,
vector <int> v2)
{
vector <int> added_vec(26);
// Adding two vector and storing
// it in another vector
for (int i = 0; i < 26; i++)
added_vec[i] = v1[i] + v2[i];
// Returning final vector
return added_vec;
}
// A recursive function that return vector
// which contains frequency of every character
vector <int> get(int pos, int l, int r,
int st, int en)
{
// If segment of this node is
// outside the given range
if (l > en || r < st)
{
vector <int> empty(26, 0);
return empty;
}
// If segment of this node is a part
// of given range, then return the
// frequency every character of the segment
if (st >= l && en <= r)
{
return seg_tree[pos];
}
// getting mid of st and en
int mid = st + en >> 1;
//storing answer of left child n v1
vector <int> v1 = get(2 * pos, l,
r, st, mid);
//storing answer of left child n v1
vector <int> v2 = get(2 * pos + 1,
l, r, mid + 1, en);
//returning the addition of both vectors
return add_two_result(v1, v2);
}
// A recursive function that update
// frequency of new and old character
void update(int pos, int indx, int st,
int en, char pre, char cur) {
// If segment of this node is
// outside the given range
if (indx > en || indx < st) return;
// Subtract frequency of previous character
seg_tree[pos][pre - 'a']--;
// Add frequency of new character
seg_tree[pos][cur - 'a']++;
if (st != en)
{
int mid = st + en >> 1;
// update left child
update(2 * pos, indx, st,
mid, pre, cur);
// update right child
update(2 * pos + 1, indx,
mid + 1, en, pre, cur);
}
}
// Utility function to
// initialize seg_tree vector
void initialize()
{
for (int i = 0; i < N; i++)
seg_tree[i].resize(26, 0);
}
int count_frequency(string s, vector <int> v)
{
int ans = 1;
// multiplying frequency of all
// characters in string hard
for (int i = 0; s[i]; i++)
ans = (ans * v[s[i] - 'a']) % mod;
return ans;
}
// Driver Code
int main()
{
int n, q, ans;
vector <int> v;
n = 15;
str = "haardhhardrddrd";
//initialize and build the seg_tree vector
initialize();
build(1, 1, n);
string s = "hard";
// getting frequency of all
// characters from 1 to 5
v = get(1, 1, 5, 1, n);
// Calling count_frequency
ans = count_frequency(s, v);
cout << ans << '\n';
// Updating character at index 3
update(1, 3, 1, n, str[2], 'x');
str[2] = 'x';
// getting frequency of all
// characters from 1 to 5
v = get(1, 1, 5, 1, n);
//calling count_frequency
ans = count_frequency(s, v);
cout << ans << '\n';
return 0;
}
Java
// Java implementation of the approach
import java.util.*;
class GFG {
final static int N = 400005;
final static int mod = 1000000007;
static int[][] seg_tree = new int[N][26];
static StringBuilder str;
// A recursive function that constructs
// Segment Tree for given String
static void build(int pos, int st, int en) {
if (st == en) {
// Increment the frequency of character
// by one if st is equal to en
seg_tree[pos][str.charAt(st - 1) - 'a']++;
return;
}
int mid = st + en >> 1;
// Build the segment tree for range st to mid
build(2 * pos, st, mid);
// Build the segment tree for range mid+1 to en
build(2 * pos + 1, mid + 1, en);
// It stores addition of frequency of
// characters of both of its child after
// segment tree is build
for (int i = 0; i < 26; i++)
seg_tree[pos][i] = seg_tree[2 * pos + 1][i] + seg_tree[2 * pos][i];
}
// A utility function for
// addition of two vectors
static int[] add_two_result(int[] v1, int[] v2) {
int[] added_vec = new int[26];
// Adding two vector and storing
// it in another vector
for (int i = 0; i < 26; i++)
added_vec[i] = v1[i] + v2[i];
// Returning final vector
return added_vec;
}
// A recursive function that return vector
// which contains frequency of every character
static int[] get(int pos, int l, int r, int st, int en) {
// If segment of this node is
// outside the given range
if (l > en || r < st) {
int[] empty = new int[26];
return empty;
}
// If segment of this node is a part
// of given range, then return the
// frequency every character of the segment
if (st >= l && en <= r) {
return seg_tree[pos];
}
// getting mid of st and en
int mid = st + en >> 1;
// storing answer of left child n v1
int[] v1 = get(2 * pos, l, r, st, mid);
// storing answer of left child n v1
int[] v2 = get(2 * pos + 1, l, r, mid + 1, en);
// returning the addition of both vectors
return add_two_result(v1, v2);
}
// A recursive function that update
// frequency of new and old character
static void update(int pos, int indx, int st, int en, char pre, char cur) {
// If segment of this node is
// outside the given range
if (indx > en || indx < st)
return;
// Subtract frequency of previous character
seg_tree[pos][pre - 'a']--;
// Add frequency of new character
seg_tree[pos][cur - 'a']++;
if (st != en) {
int mid = st + en >> 1;
// update left child
update(2 * pos, indx, st, mid, pre, cur);
// update right child
update(2 * pos + 1, indx, mid + 1, en, pre, cur);
}
}
static int count_frequency(String s, int[] v) {
int ans = 1;
// multiplying frequency of all
// characters in String hard
for (int i = 0; i < s.length(); i++)
ans = (ans * v[s.charAt(i) - 'a']) % mod;
return ans;
}
// Driver Code
public static void main(String[] args) {
int n, q, ans;
int[] v;
n = 15;
str = new StringBuilder("haardhhardrddrd");
build(1, 1, n);
String s = "hard";
// getting frequency of all
// characters from 1 to 5
v = get(1, 1, 5, 1, n);
// Calling count_frequency
ans = count_frequency(s, v);
System.out.println(ans);
// Updating character at index 3
update(1, 3, 1, n, str.charAt(2), 'x');
str.setCharAt(2, 'x');
// getting frequency of all
// characters from 1 to 5
v = get(1, 1, 5, 1, n);
// calling count_frequency
ans = count_frequency(s, v);
System.out.println(ans);
}
}
// This code is contributed by
// sanjeev2552
Python3
# Python3 implementation of the approach
N = 400005
mod = 1000000007
seg_tree = [[0 for i in range(26)] for i in range(N)]
str = ""
# A recursive function that constructs
# Segment Tree for given
def build(pos, st, en):
if (st == en):
# Increment the frequency of character
# by one if st is equal to en
seg_tree[pos][ord(str[st - 1] )- ord('a')]+=1
return
mid = st + en >> 1
# Build the segment tree for range st to mid
build(2 * pos, st, mid)
# Build the segment tree for range mid+1 to en
build(2 * pos + 1, mid + 1, en)
# It stores addition of frequency of
# characters of both of its child after
# segment tree is build
for i in range(26):
seg_tree[pos][i] = seg_tree[2 * pos + 1][i] + \
seg_tree[2 * pos][i]
# A utility function for
# addition of two vectors
def add_two_result(v1,v2):
added_vec=[0]*(26)
# Adding two vector and storing
# it in another vector
for i in range(26):
added_vec[i] = v1[i] + v2[i]
# Returning final vector
return added_vec
# A recursive function that return vector
# which contains frequency of every character
def get(pos, l, r,st, en):
# If segment of this node is
# outside the given range
if (l > en or r < st):
empty = [0]*26
return empty
# If segment of this node is a part
# of given range, then return the
# frequency every character of the segment
if (st >= l and en <= r):
return seg_tree[pos]
# getting mid of st and en
mid = st + en >> 1
# storing answer of left child n v1
v1 = get(2 * pos, l,r, st, mid)
# storing answer of left child n v1
v2 = get(2 * pos + 1,l, r, mid + 1, en)
# returning the addition of both vectors
return add_two_result(v1, v2)
# A recursive function that update
# frequency of new and old character
def update(pos, indx, st,en,pre,cur):
# If segment of this node is
# outside the given range
if (indx > en or indx < st):
return
# Subtract frequency of previous character
seg_tree[pos][ord(pre) - ord('a')]-=1
# Add frequency of new character
seg_tree[pos][ord(cur) - ord('a')]+=1
if (st != en):
mid = st + en >> 1
# update left child
update(2 * pos,indx, st,mid, pre, cur)
# update right child
update(2 * pos + 1, indx,mid + 1, en, pre, cur)
def count_frequency(s,v):
ans = 1
# multiplying frequency of all
# characters in hard
i = 0
while i < len(s):
ans = (ans * v[ord(s[i]) - ord('a')]) % mod
i += 1
return ans
# Driver Code
if __name__ == '__main__':
v=[]
n = 15
str = "haardhhardrddrd"
str=[i for i in str]
build(1, 1, n)
s = "hard"
# getting frequency of all
# characters from 1 to 5
v = get(1, 1, 5, 1, n)
# Calling count_frequency
ans = count_frequency(s, v)
print(ans)
# Updating character at index 3
update(1, 3, 1, n, str[2], 'x')
str[2] = 'x'
# getting frequency of all
# characters from 1 to 5
v = get(1, 1, 5, 1, n)
# calling count_frequency
ans = count_frequency(s, v)
print(ans)
# This code is contributed by mohit kumar 29
C#
// C# implementation of the approach
using System;
using System.Text;
class GFG{
readonly static int N = 400005;
readonly static int mod = 1000000007;
static int[,] seg_tree = new int[N, 26];
static StringBuilder str;
// A recursive function that constructs
// Segment Tree for given String
static void build(int pos, int st, int en)
{
if (st == en)
{
// Increment the frequency of character
// by one if st is equal to en
seg_tree[pos,str[st - 1] - 'a']++;
return;
}
int mid = st + en >> 1;
// Build the segment tree for range st to mid
build(2 * pos, st, mid);
// Build the segment tree for range mid+1 to en
build(2 * pos + 1, mid + 1, en);
// It stores addition of frequency of
// characters of both of its child after
// segment tree is build
for(int i = 0; i < 26; i++)
seg_tree[pos, i] = seg_tree[2 * pos + 1, i] +
seg_tree[2 * pos, i];
}
// A utility function for
// addition of two vectors
static int[] add_two_result(int[] v1, int[] v2)
{
int[] added_vec = new int[26];
// Adding two vector and storing
// it in another vector
for(int i = 0; i < 26; i++)
added_vec[i] = v1[i] + v2[i];
// Returning readonly vector
return added_vec;
}
// A recursive function that return vector
// which contains frequency of every character
static int[] get(int pos, int l, int r, int st, int en)
{
// If segment of this node is
// outside the given range
if (l > en || r < st)
{
int[] empty = new int[26];
return empty;
}
// If segment of this node is a part
// of given range, then return the
// frequency every character of the segment
if (st >= l && en <= r)
{
return GetRow(seg_tree, pos);
}
// Getting mid of st and en
int mid = st + en >> 1;
// Storing answer of left child n v1
int[] v1 = get(2 * pos, l, r, st, mid);
// Storing answer of left child n v1
int[] v2 = get(2 * pos + 1, l, r, mid + 1, en);
// Returning the addition of both vectors
return add_two_result(v1, v2);
}
// A recursive function that update
// frequency of new and old character
static void update(int pos, int indx, int st,
int en, char pre, char cur)
{
// If segment of this node is
// outside the given range
if (indx > en || indx < st)
return;
// Subtract frequency of previous character
seg_tree[pos,pre - 'a']--;
// Add frequency of new character
seg_tree[pos,cur - 'a']++;
if (st != en)
{
int mid = st + en >> 1;
// update left child
update(2 * pos, indx, st, mid, pre, cur);
// update right child
update(2 * pos + 1, indx, mid + 1,
en, pre, cur);
}
}
static int count_frequency(String s, int[] v)
{
int ans = 1;
// Multiplying frequency of all
// characters in String hard
for(int i = 0; i < s.Length; i++)
ans = (ans * v[s[i] - 'a']) % mod;
return ans;
}
public static int[] GetRow(int[,] matrix, int row)
{
var rowLength = matrix.GetLength(1);
var rowVector = new int[rowLength];
for(var i = 0; i < rowLength; i++)
rowVector[i] = matrix[row, i];
return rowVector;
}
// Driver Code
public static void Main(String[] args)
{
int n, ans;
int[] v;
n = 15;
str = new StringBuilder("haardhhardrddrd");
build(1, 1, n);
String s = "hard";
// Getting frequency of all
// characters from 1 to 5
v = get(1, 1, 5, 1, n);
// Calling count_frequency
ans = count_frequency(s, v);
Console.WriteLine(ans);
// Updating character at index 3
update(1, 3, 1, n, str[2], 'x');
str[2] = 'x';
// Getting frequency of all
// characters from 1 to 5
v = get(1, 1, 5, 1, n);
// Calling count_frequency
ans = count_frequency(s, v);
Console.WriteLine(ans);
}
}
// This code is contributed by shikhasingrajput
Javascript
<script>
// Javascript implementation of the approach
var N = 400005;
var mod = 1000000007;
var seg_tree = Array.from(Array(N), ()=>Array(26).fill(0));
var str = "";
// A recursive function that constructs
// Segment Tree for given String
function build(pos, st, en)
{
if (st == en)
{
// Increment the frequency of character
// by one if st is equal to en
seg_tree[pos][str[st - 1].charCodeAt(0) - 'a'.charCodeAt(0)]++;
return;
}
var mid = st + en >> 1;
// Build the segment tree for range st to mid
build(2 * pos, st, mid);
// Build the segment tree for range mid+1 to en
build(2 * pos + 1, mid + 1, en);
// It stores addition of frequency of
// characters of both of its child after
// segment tree is build
for(var i = 0; i < 26; i++)
seg_tree[pos][ i] = seg_tree[2 * pos + 1][ i] +
seg_tree[2 * pos][ i];
}
// A utility function for
// addition of two vectors
function add_two_result(v1, v2)
{
var added_vec = Array(26).fill(0);
// Adding two vector and storing
// it in another vector
for(var i = 0; i < 26; i++)
added_vec[i] = v1[i] + v2[i];
// Returning readonly vector
return added_vec;
}
// A recursive function that return vector
// which contains frequency of every character
function get(pos, l, r, st, en)
{
// If segment of this node is
// outside the given range
if (l > en || r < st)
{
var empty = Array(26).fill(0);
return empty;
}
// If segment of this node is a part
// of given range, then return the
// frequency every character of the segment
if (st >= l && en <= r)
{
return GetRow(seg_tree, pos);
}
// Getting mid of st and en
var mid = st + en >> 1;
// Storing answer of left child n v1
var v1 = get(2 * pos, l, r, st, mid);
// Storing answer of left child n v1
var v2 = get(2 * pos + 1, l, r, mid + 1, en);
// Returning the addition of both vectors
return add_two_result(v1, v2);
}
// A recursive function that update
// frequency of new and old character
function update(pos, indx, st, en, pre, cur)
{
// If segment of this node is
// outside the given range
if (indx > en || indx < st)
return;
// Subtract frequency of previous character
seg_tree[pos][pre.charCodeAt(0) - 'a'.charCodeAt(0)]--;
// Add frequency of new character
seg_tree[pos][cur.charCodeAt(0) - 'a'.charCodeAt(0)]++;
if (st != en)
{
var mid = st + en >> 1;
// update left child
update(2 * pos, indx, st, mid, pre, cur);
// update right child
update(2 * pos + 1, indx, mid + 1,
en, pre, cur);
}
}
function count_frequency(s, v)
{
var ans = 1;
// Multiplying frequency of all
// characters in String hard
for(var i = 0; i < s.length; i++)
ans = (ans * v[s[i].charCodeAt(0) - 'a'.charCodeAt(0)]) % mod;
return ans;
}
function GetRow(matrix, row)
{
var rowLength = matrix[0].length;
var rowVector = Array(rowLength).fill(0);
for(var i = 0; i < rowLength; i++)
rowVector[i] = matrix[row][i];
return rowVector;
}
// Driver Code
var n, ans;
var v = [];
n = 15;
str = "haardhhardrddrd".split('');
build(1, 1, n);
var s = "hard";
// Getting frequency of all
// characters from 1 to 5
v = get(1, 1, 5, 1, n);
// Calling count_frequency
ans = count_frequency(s, v);
document.write(ans+"<br>");
// Updating character at index 3
update(1, 3, 1, n, str[2], 'x');
str[2] = 'x';
// Getting frequency of all
// characters from 1 to 5
v = get(1, 1, 5, 1, n);
// Calling count_frequency
ans = count_frequency(s, v);
document.write(ans);
// This code is contributed by rrrtnx.
</script>
Producción
2 1
Complejidad de tiempo: 0(m*log(n)+n*log(n))
Espacio auxiliar: O(n)
Tema relacionado: Árbol de segmentos
Publicación traducida automáticamente
Artículo escrito por saurabh_dtu y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA