Categoría: Segment-Tree

Los 10 mejores algoritmos y estructuras de datos para la programación competitiva

Posted on by Rudeus Greyrat

  En esta publicación, discutiremos los 10 algoritmos y estructuras de datos más importantes para la codificación competitiva. Temas:  Algoritmos gráficos Programación dinámica Buscando y Ordenando: Teoría de Números y Otras Matemáticas Algoritmos de flujo geométrico y de red Estructuras de datos Los enlaces a continuación cubren los algoritmos más importantes y los temas de … Continue reading «Los 10 mejores algoritmos y estructuras de datos para la programación competitiva»

Número lexicográfico más pequeño después de un máximo de K intercambios consecutivos

Posted on by Rudeus Greyrat

Dado un número en forma de string str y un entero K , la tarea es encontrar el entero más pequeño que se puede formar después de realizar como máximo K intercambios consecutivos. Los intercambios consecutivos significan que en un intercambio el carácter en el índice i puede intercambiarse con el carácter en el índice … Continue reading «Número lexicográfico más pequeño después de un máximo de K intercambios consecutivos»

Descomposición ligera pesada | Serie 1 (Introducción)

Posted on by Rudeus Greyrat

La descomposición Heavy Light (HLD) es una de las técnicas más utilizadas en la programación competitiva . Problema de ejemplo: comprendamos la descomposición pesada-ligera (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 árbol para … Continue reading «Descomposición ligera pesada | Serie 1 (Introducción)»

Número de números primos en un subarreglo (con actualizaciones)

Posted on by Rudeus Greyrat

Dada una array de N enteros, la tarea es realizar las siguientes dos consultas:  query(start, end) : Imprime el número de números primos en el subarreglo de principio a fin  update(i, x) : actualiza el valor en el índice i a x, es decir, arr[i] = x Ejemplos:   Input : arr = {1, 2, 3, … Continue reading «Número de números primos en un subarreglo (con actualizaciones)»

Encuentre valor después de N operaciones para eliminar N caracteres de la string S con restricciones dadas

Posted on by Rudeus Greyrat

Dada una string S de tamaño N. Inicialmente, el valor de count es 0 . La tarea es encontrar el valor de count después de N operaciones para eliminar todos los N caracteres de la string S dada, donde cada operación es: En cada operación, seleccione alfabéticamente el carácter más pequeño de la string S … Continue reading «Encuentre valor después de N operaciones para eliminar N caracteres de la string S con restricciones dadas»

Árboles de segmentos | (Producto de Rango Módulo m 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  1 Encontrar el producto de elementos de índice l a r donde 0 <= l <= r <= n-1 tomar su módulo por un entero m. 2 Cambiar el valor de un elemento … Continue reading «Árboles de segmentos | (Producto de Rango Módulo m dado)»

LIS utilizando el árbol de segmentos

Posted on by Rudeus Greyrat

Se le da una array de números enteros, necesita encontrar la longitud de la subsecuencia creciente más larga. Puede haber 4 enfoques para resolver el problema. 1) Fuerza bruta:  en este enfoque, intentamos encontrar todas las subsecuencias crecientes y luego devolver la longitud máxima de la subsecuencia creciente más larga. Para hacer esto, hacemos uso … Continue reading «LIS utilizando el árbol de segmentos»

Distancia máxima entre dos 1 en una array binaria en un rango dado

Posted on by Rudeus Greyrat

Dada una array binaria de tamaño N y un rango en [l, r] , la tarea es encontrar la distancia máxima entre dos 1 en este rango dado. Ejemplos:  Entrada: arr = {1, 0, 0, 1}, l = 0, r = 3  Salida: 3  En el rango dado de 0 a 3, el primer 1 … Continue reading «Distancia máxima entre dos 1 en una array binaria en un rango dado»

Programa Python3 para consultas LCM de rango

Posted on by Rudeus Greyrat

Dada una array de enteros, evalúe consultas de la forma LCM(l, r). Puede haber muchas consultas, por lo tanto, evalúe las consultas de manera eficiente.   LCM (l, r) denotes the LCM of array elements that lie between the index l and r (inclusive of both indices) Mathematically, LCM(l, r) = LCM(arr[l], arr[l+1] , ……… , … Continue reading «Programa Python3 para consultas LCM de rango»

Árbol de segmentos | Implementación eficiente

Posted on by Rudeus Greyrat

Consideremos el siguiente problema para comprender los árboles de segmentos sin recursividad. Tenemos una array arr[0 . . . n-1]. Deberíamos poder,   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 | Implementación eficiente»