Categoría: Segment-Tree

Cuente las substrings que tienen una frecuencia de un carácter que excede la de otro carácter en una string

Posted on by Rudeus Greyrat

Dada una string S de tamaño N que consta solo de caracteres a , b y c , la tarea es encontrar el número de substrings de la string S tal que la frecuencia del carácter a sea mayor que la frecuencia del carácter c . Ejemplos: Entrada: S = “abcc” Salida: 2 Explicación: A … Continue reading «Cuente las substrings que tienen una frecuencia de un carácter que excede la de otro carácter en una string»

Maximice la suma de la array reduciendo los elementos de la array para que no contengan tripletes (i, j, k) donde a[i] < a[j] y a[i] < a[k] y j <i <k

Posted on by Rudeus Greyrat

Dada una array arr[] que consta de N enteros, la tarea es encontrar la suma máxima de una array formada por la disminución de los elementos de la array en 1 cualquier número de veces (posiblemente cero) de modo que no haya tripletes (i, j, k) ( indexación basada en 1 ) tal que arr[j] … Continue reading «Maximice la suma de la array reduciendo los elementos de la array para que no contengan tripletes (i, j, k) donde a[i] < a[j] y a[i] < a[k] y j <i <k»

Consulta para encontrar la longitud del subarreglo más largo que consiste solo en 1s

Posted on by Rudeus Greyrat

Dada una array binaria arr[] de tamaño N y una array 2D Q[][] que contiene K consultas de los siguientes dos tipos: 1 : Imprime la longitud del subarreglo más largo que consta de solo 1 s. 2 X : Voltee el elemento en el índice X ( indexación basada en 1 ), es decir, … Continue reading «Consulta para encontrar la longitud del subarreglo más largo que consiste solo en 1s»

Longitud del subarreglo más largo con los mismos elementos en incrementos de K como máximo

Posted on by Rudeus Greyrat

Dada una array de enteros arr y un número K , la tarea es encontrar la longitud del subarreglo más largo de modo que todos los elementos en este subarreglo puedan hacerse iguales en incrementos de K como máximo. Ejemplos:  Entrada: arr[] = {2, 0, 4, 6, 7}, K = 6  Salida: 3  El subarreglo … Continue reading «Longitud del subarreglo más largo con los mismos elementos en incrementos de K como máximo»

Programa Javascript para encontrar la suma de la array usando Bitwise O después de dividir la array dada en dos mitades después de K cambios circulares

Posted on by Rudeus Greyrat

Dada una array A[] de longitud N , donde N es un número par, la tarea es responder Q consultas independientes donde cada consulta consiste en un número entero positivo K que representa el número de desplazamientos circulares realizados en la array y encontrar la suma de elementos realizando la operación Bitwise OR en la … Continue reading «Programa Javascript para encontrar la suma de la array usando Bitwise O después de dividir la array dada en dos mitades después de K cambios circulares»

Árbol de segmentos | Conjunto 1 (suma del rango dado)

Posted on by Rudeus Greyrat

Consideremos el siguiente problema para comprender los árboles de segmentos. Tenemos una array arr[0 . . . n-1]. Deberíamos ser capaces de  Encuentre la suma de elementos del índice l a r donde 0 <= l <= r <= n-1 Cambia el valor de un elemento específico de la array a un nuevo valor x. … Continue reading «Árbol de segmentos | Conjunto 1 (suma del rango dado)»

Consulta para comprobar si un rango está formado por elementos consecutivos

Posted on by Rudeus Greyrat

Dada una array de n enteros no consecutivos y Q consultas, la tarea es verificar si para el rango l y r dado , los elementos son consecutivos o no. Ejemplos:   Entrada: arr = { 2, 4, 3, 7, 6, 1}, Q = { (1, 3), (3, 5), (5, 6) }  Salida: Sí, No, No  … Continue reading «Consulta para comprobar si un rango está formado por elementos consecutivos»

Descomposición ligera pesada | Conjunto 2 (Implementación)

Posted on by Rudeus Greyrat

Recomendamos encarecidamente consultar la publicación a continuación como requisito previo para esto. Descomposición ligera pesada | Conjunto 1 (Introducción) En la publicación anterior, discutimos la descomposición Heavy-light (HLD) con la ayuda del siguiente ejemplo. Supongamos que tenemos un árbol desequilibrado (no necesariamente un árbol binario) de n Nodes , y tenemos que realizar operaciones en el … Continue reading «Descomposición ligera pesada | Conjunto 2 (Implementación)»

Propagación diferida en el árbol de segmentos | conjunto 2

Posted on by Rudeus Greyrat

Dada una array arr[] de tamaño N . Hay dos tipos de operaciones:   Actualizar (l, r, x): Incremente el a[i] (l <= i <= r) con el valor x. Query(l, r) : encuentre el valor máximo en la array en un rango de l a r (ambos están incluidos). Ejemplos:   Entrada: arr[] = {1, 2, … Continue reading «Propagación diferida en el árbol de segmentos | conjunto 2»

Suma de intervalo y actualización con número de divisores

Posted on by Rudeus Greyrat

Dada una array A de N enteros. Debe responder dos tipos de consultas: 1. Actualizar [l, r]: para cada i en el rango de l a r, actualice A i con D (A i ), donde D (A i ) representa el número de divisores de A i 2. Consulta [l, r]: calcule la suma … Continue reading «Suma de intervalo y actualización con número de divisores»