Esta guía compila una serie de algoritmos y estructuras de datos fundamentales, categorizados para facilitar su consulta y aplicación en problemas de programación.
Estrategias Algorítmicas Comunes
- Programación Dinámica (DP)
- Algoritmos Voraces (Greedy)
- Búsqueda Binaria
El corazón de estos métodos reside en la identificación de patrones y la observación de propiedades clave. A menudo, se combinan con estructuras de datos avanzadas como:
- Barrido de Líneas
- Árboles de Segmentos
- Árboles Fenwick (BIT)
- Árboles Balanceados (Treap, Splay)
- Colas de Prioridad (Heaps)
- Pilas y Colas Monótonas
Técnicas de Resolución de Problemas
- Invertir el problema (resolver lo opuesto)
- División por Raíz Cuadrada
- Consideración de Prefijos/Sufijos
- Descomposición de Contribuciones
- Transformación de Problemas
Algoritmos de Cadenas
Algoritmo KMP para Búsqueda de Patrones
El algoritmo Knuth-Morris-Pratt (KMP) es un método eficiente para encontrar ocurrencias de una "palabra" (patrón) dentro de un "texto" más largo. Evita revisitar caracteres del texto, utilizando una función de prefijo para saber cuántos caracteres ya comparados se pueden "saltar".
#include <iostream>
#include <vector>
#include <string>
#include <cstdio> // Para scanf/printf
// Función para lectura rápida de enteros (común en programación competitiva)
long long leer_entero() {
long long val = 0;
int signo = 1;
char c = getchar();
while (c < '0' || c > '9') {
if (c == '-') signo = -1;
c = getchar();
}
while (c >= '0' && c <= '9') {
val = (val << 1) + (val << 3) + c - '0';
c = getchar();
}
return val * signo;
}
const int MAX_LEN = 1000000 + 10;
char texto_principal[MAX_LEN];
char patron_busqueda[MAX_LEN];
int tabla_prefijo[MAX_LEN]; // Almacena la longitud del prefijo propio más largo que también es sufijo
int longitud_texto, longitud_patron;
std::vector<int> indices_coincidencia;
int main() {
// Lectura del texto y el patrón (se usa scanf para cadenas)
scanf("%s%s", texto_principal + 1, patron_busqueda + 1); // Indexación basada en 1
longitud_texto = strlen(texto_principal + 1);
longitud_patron = strlen(patron_busqueda + 1);
// Construcción de la tabla de prefijo (función de fallo)
// tabla_prefijo[i] = longitud del prefijo propio más largo de patron_busqueda[1...i] que también es sufijo
for (int i = 2, j = 0; i <= longitud_patron; ++i) {
while (j > 0 && patron_busqueda[i] != patron_busqueda[j + 1]) {
j = tabla_prefijo[j]; // Retrocede usando la tabla de prefijo
}
if (patron_busqueda[i] == patron_busqueda[j + 1]) {
j++; // Si los caracteres coinciden, extiende el prefijo
}
tabla_prefijo[i] = j;
}
// Búsqueda del patrón en el texto principal
for (int i = 1, j = 0; i <= longitud_texto; ++i) {
while (j > 0 && texto_principal[i] != patron_busqueda[j + 1]) {
j = tabla_prefijo[j]; // Retrocede usando la tabla de prefijo
}
if (texto_principal[i] == patron_busqueda[j + 1]) {
j++; // Si los caracteres coinciden, extiende la coincidencia
}
if (j == longitud_patron) { // Se encontró una ocurrencia completa
// Almacena el índice de inicio de la coincidencia en el texto (basado en 1)
indices_coincidencia.push_back(i - longitud_patron + 1);
j = tabla_prefijo[j]; // Continúa buscando después de la coincidencia
}
}
// Imprimir los índices donde se encuentra el patrón
for (int idx : indices_coincidencia) {
printf("%d\n", idx);
}
// Imprimir la tabla de prefijo (bordes)
for (int i = 1; i <= longitud_patron; ++i) {
printf("%d ", tabla_prefijo[i]);
}
printf("\n");
return 0;
}
Arreglos de Sufijos
Un arreglo de sufijos es una estructura de datos que almacena las posiciones de inicio de todos los sufijos de una cadena en orden lexicográfico. Se utiliza para resolver una variedad de problemas de cadenas de manera eficiente.
#include <iostream>
#include <string>
#include <vector>
#include <cstring> // Para strlen, memset, memcpy
#include <algorithm> // Para sort, max
const int MAXN_SUFIJOS = 1000000 + 5;
char cadena_entrada[MAXN_SUFIJOS];
int sa_arreglo[MAXN_SUFIJOS]; // Suffix Array: sa_arreglo[i] = índice del i-ésimo sufijo más pequeño
int rank_sufijo[MAXN_SUFIJOS]; // rank_sufijo[i] = rango del sufijo que comienza en i
int old_rank_val[MAXN_SUFIJOS * 2]; // Para comparar pares de rangos
int temp_indices[MAXN_SUFIJOS]; // Auxiliar para el conteo de ordenación
int conteo_chars[MAXN_SUFIJOS]; // Para el conteo de ordenación
// Comparador para ordenar los sufijos por rangos (usado en el algoritmo SA)
// Compara dos sufijos (que empiezan en 'a' y 'b') usando sus rangos actuales y los de sus partes 'w' siguientes.
bool comparar_sufijos(int idx_a, int idx_b, int width) {
return old_rank_val[idx_a] == old_rank_val[idx_b] && old_rank_val[idx_a + width] == old_rank_val[idx_b + width];
}
int main() {
scanf("%s", cadena_entrada + 1); // Indexación basada en 1
int n_longitud = strlen(cadena_entrada + 1);
int max_char_val = 128; // Rango de caracteres ASCII
// Inicialización del conteo y rank_sufijo con los caracteres individuales
for (int i = 1; i <= n_longitud; ++i) {
conteo_chars[rank_sufijo[i] = cadena_entrada[i]]++;
}
// Calcular prefijos acumulados para el conteo de ordenación
for (int i = 1; i <= max_char_val; ++i) {
conteo_chars[i] += conteo_chars[i - 1];
}
// Primera ordenación por caracteres individuales
for (int i = n_longitud; i >= 1; --i) {
sa_arreglo[conteo_chars[rank_sufijo[i]]--] = i;
}
int num_rank_clases = 0; // Número de clases de rango distintas
// Algoritmo de Doble para construir el SA
// 'width' se duplica en cada iteración: 1, 2, 4, 8, ...
for (int width = 1; ; width <<= 1, max_char_val = num_rank_clases, num_rank_clases = 0) {
// Preparar temp_indices para la segunda clave (sufijos de longitud 'width')
// Primero, los sufijos que empiezan en n-width+1 ... n
// Estos no tienen una parte "width" siguiente, se consideran los más pequeños
for (int i = n_longitud - width + 1; i <= n_longitud; ++i) {
temp_indices[++num_rank_clases] = i;
}
// Luego, el resto de sufijos ordenados por la primera clave (la parte actual)
for (int i = 1; i <= n_longitud; ++i) {
if (sa_arreglo[i] > width) {
temp_indices[++num_rank_clases] = sa_arreglo[i] - width;
}
}
// Realizar conteo de ordenación con la primera clave (rank_sufijo)
memset(conteo_chars, 0, sizeof(conteo_chars));
for (int i = 1; i <= n_longitud; ++i) {
conteo_chars[rank_sufijo[i]]++;
}
for (int i = 1; i <= max_char_val; ++i) {
conteo_chars[i] += conteo_chars[i - 1];
}
for (int i = n_longitud; i >= 1; --i) {
sa_arreglo[conteo_chars[rank_sufijo[temp_indices[i]]]--] = temp_indices[i];
}
// Actualizar los rangos
num_rank_clases = 0;
memcpy(old_rank_val, rank_sufijo, sizeof(rank_sufijo)); // Guardar rangos anteriores
for (int i = 1; i <= n_longitud; ++i) {
// Si el sufijo actual y el anterior son iguales, tienen el mismo rango
rank_sufijo[sa_arreglo[i]] = comparar_sufijos(sa_arreglo[i-1], sa_arreglo[i], width) ? num_rank_clases : ++num_rank_clases;
}
if (num_rank_clases == n_longitud) break; // Todos los sufijos tienen rangos únicos
}
// Calcular el LCP (Longest Common Prefix) array (altura)
// lcp_arreglo[i] = Longitud del prefijo común más largo entre sa_arreglo[i] y sa_arreglo[i-1]
std::vector<int> lcp_arreglo(n_longitud + 1, 0);
int current_lcp = 0;
for (int i = 1; i <= n_longitud; ++i) {
if (rank_sufijo[i] == 0) continue; // Primer sufijo no tiene LCP con uno anterior
if (current_lcp) current_lcp--; // Propiedad del LCP: LCP(i, j) >= LCP(i-1, j+1)-1
int prev_suf_idx = sa_arreglo[rank_sufijo[i] - 1]; // Índice del sufijo anterior en orden SA
while (i + current_lcp <= n_longitud && prev_suf_idx + current_lcp <= n_longitud &&
cadena_entrada[i + current_lcp] == cadena_entrada[prev_suf_idx + current_lcp]) {
current_lcp++;
}
lcp_arreglo[rank_sufijo[i]] = current_lcp;
}
// Imprimir el arreglo de sufijos (SA)
for (int i = 1; i <= n_longitud; ++i) {
printf("%d ", sa_arreglo[i]);
}
printf("\n");
return 0;
}
Matemáticas
Multiplicación Modular Robusta (龟速乘)
Esta función calcula (x * y) % p de forma segura para números grandes, donde x * y podría exceder la capacidad de un long long. Utiliza el método de multiplicación binaria (similar a la exponenciación binaria) para sumar x, y veces, todo módulo p.
long long multiplicacion_modular(long long base, long long factor, long long modulo) {
long long resultado = 0;
base %= modulo; // Asegurar que base esté dentro del rango modular
while (factor > 0) {
if (factor & 1) { // Si factor es impar, sumar base al resultado
resultado = (resultado + base) % modulo;
}
base = (base * 2) % modulo; // Duplicar base
factor >>= 1; // Dividir factor por 2
}
return resultado;
}
Búsqueda Ternaria
La búsqueda ternaria es un algoritmo para encontrar el mínimo o máximo de una función unimodal en un intervalo continuo. Divide el intervalo en tres partes y descarta un tercio en cada iteración.
#include <iostream>
#include <vector>
#include <cmath> // Para fabs
#include <algorithm> // Para max
#include <iomanip> // Para setprecision
const int MAX_FUNC = 100000 + 5;
double coef_a[MAX_FUNC], coef_b[MAX_FUNC], coef_c[MAX_FUNC];
int num_funciones;
// Función a optimizar (encontrar el máximo de un conjunto de parábolas)
// Evalúa el valor máximo de a[i]*x*x + b[i]*x + c[i] para un dado x
double evaluar_max_parabola(double punto_x) {
double valor_maximo = -1e18; // Inicializar con un valor muy pequeño
for (int i = 1; i <= num_funciones; ++i) {
valor_maximo = std::max(valor_maximo, coef_a[i] * punto_x * punto_x + coef_b[i] * punto_x + coef_c[i]);
}
return valor_maximo;
}
// Función para lectura rápida de enteros
long long leer_entero_rapido() {
long long val = 0;
int signo = 1;
char c = getchar();
while (c < '0' || c > '9') {
if (c == '-') signo = -1;
c = getchar();
}
while (c >= '0' && c <= '9') {
val = (val << 1) + (val << 3) + c - '0';
c = getchar();
}
return val * signo;
}
void resolver_caso() {
num_funciones = leer_entero_rapido();
for (int i = 1; i <= num_funciones; ++i) {
coef_a[i] = leer_entero_rapido();
coef_b[i] = leer_entero_rapido();
coef_c[i] = leer_entero_rapido();
}
double limite_izquierdo = 0.0;
double limite_derecho = 1000.0; // Rango de búsqueda para x
const double EPSILON = 1e-7; // Precisión deseada
// Búsqueda Ternaria
while (limite_derecho - limite_izquierdo > EPSILON) {
double p1 = limite_izquierdo + (limite_derecho - limite_izquierdo) / 3.0;
double p2 = limite_derecho - (limite_derecho - limite_izquierdo) / 3.0;
// Si f(p1) < f(p2), el máximo está a la derecha de p1
if (evaluar_max_parabola(p1) < evaluar_max_parabola(p2)) {
limite_izquierdo = p1;
} else { // Si f(p1) >= f(p2), el máximo está a la izquierda de p2
limite_derecho = p2;
}
}
// El punto óptimo es 'limite_izquierdo' (o 'limite_derecho', son casi iguales)
printf("%.4lf\n", evaluar_max_parabola(limite_izquierdo));
}
int main() {
int num_casos = leer_entero_rapido();
while (num_casos--) {
resolver_caso();
}
return 0;
}
Teorema de Euler Generalizado
El teorema de Euler generalizado, o teorema de la totient de Euler extendido, se utiliza para calcular \(a^b \pmod m\) incluso cuando \(b\) es muy grande o \(b \ge \phi(m)\). Establece que:
- Si \(b < \phi(m)\), entonces \(a^b \equiv a^b \pmod m\).
- Si \(b \ge \phi(m)\), entonces \(a^b \equiv a^{b \pmod{\phi(m)} + \phi(m)} \pmod m\).
#include <iostream>
#include <cmath> // Para sqrt
#include <string>
#include <cstdio> // Para getchar
// Función para lectura rápida de enteros
long long leer_long_largo() {
long long val = 0;
int signo = 1;
char c = getchar();
while (c < '0' || c > '9') {
if (c == '-') signo = -1;
c = getchar();
}
while (c >= '0' && c <= '9') {
val = (val << 1) + (val << 3) + c - '0';
c = getchar();
}
return val * signo;
}
// Función que calcula la función totient de Euler phi(x)
long long calcular_phi(long long numero) {
if (numero == 1) return 1; // phi(1) = 1
long long resultado = numero;
for (long long i = 2; i * i <= numero; ++i) {
if (numero % i == 0) {
resultado = resultado / i * (i - 1);
while (numero % i == 0) {
numero /= i;
}
}
}
if (numero > 1) { // Si queda un factor primo mayor que sqrt(numero)
resultado = resultado / numero * (numero - 1);
}
return resultado;
}
// Función de exponenciación modular (a^b % m)
long long exponenciacion_modular(long long base, long long exp, long long modulo) {
long long res = 1;
base %= modulo;
while (exp > 0) {
if (exp & 1) { // Si exp es impar
res = res * base % modulo;
}
base = base * base % modulo; // base = base^2 % modulo
exp >>= 1; // exp = exp / 2
}
return res;
}
int main() {
long long base_n = leer_long_largo();
long long modulo_p = leer_long_largo();
long long phi_de_p = calcular_phi(modulo_p);
long long exponente_val = 0;
bool exponente_mayor_que_phi = false; // Flag para indicar si el exponente es ≥ phi(p)
// Leer el exponente como una cadena para manejar números muy grandes
char c_char = getchar(); // Consumir el salto de línea después del segundo long long
// Saltar cualquier espacio en blanco antes del número
while (c_char < '0' || c_char > '9') {
c_char = getchar();
}
// Procesa el exponente dígito por dígito
// Si el exponente excederá phi_de_p, solo necesitamos su valor módulo phi_de_p,
// y activar el flag exponente_mayor_que_phi
while (c_char >= '0' && c_char <= '9') {
exponente_val = exponente_val * 10 + (c_char - '0');
if (exponente_val >= phi_de_p) {
exponente_mayor_que_phi = true;
exponente_val %= phi_de_p;
}
c_char = getchar();
}
// Aplicar el teorema de Euler extendido
// Si el exponente original (m) era ≥ phi(p), sumar phi(p) al exponente reducido
if (exponente_mayor_que_phi) {
exponente_val += phi_de_p;
}
printf("%lld\n", exponenciacion_modular(base_n, exponente_val, modulo_p));
return 0;
}
Interpolación de Lagrange
La interpolación de Lagrange es un método para encontrar un polinomio de grado mínimo que pasa por un conjunto dado de puntos \((x_i, y_i)\). La fórmula es:
\[f(x) = \sum\limits_{i=1}^n y_i \prod\limits_{j=1, j \ne i}^n \dfrac{x - x_j}{x_i - x_j}\]
#include <iostream>
#include <vector>
#include <cstdio> // Para getchar
const int MAX_PUNTOS = 2000 + 10;
const long long MODULO = 998244353; // Un módulo primo común
long long puntos_x[MAX_PUNTOS];
long long puntos_y[MAX_PUNTOS];
int cantidad_puntos;
long long valor_a_evaluar;
// Función para lectura rápida de long long
long long leer_long_largo() {
long long val = 0;
int signo = 1;
char c = getchar();
while (c < '0' || c > '9') {
if (c == '-') signo = -1;
c = getchar();
}
while (c >= '0' && c <= '9') {
val = (val << 1) + (val << 3) + c - '0';
c = getchar();
}
return val * signo;
}
// Función de exponenciación modular (x^y % MODULO)
long long potencia_modular(long long base, long long exponente) {
long long resultado = 1;
base %= MODULO;
while (exponente > 0) {
if (exponente & 1) resultado = resultado * base % MODULO;
base = base * base % MODULO;
exponente >>= 1;
}
return resultado;
}
// Función para calcular el inverso modular (a^(MODULO-2) % MODULO)
long long inverso_modular(long long num) {
return potencia_modular(num, MODULO - 2);
}
int main() {
cantidad_puntos = leer_long_largo();
valor_a_evaluar = leer_long_largo();
for (int i = 1; i <= cantidad_puntos; ++i) {
puntos_x[i] = leer_long_largo();
puntos_y[i] = leer_long_largo();
}
long long resultado_final = 0;
// Sumatoria principal para la fórmula de Lagrange
for (int i = 1; i <= cantidad_puntos; ++i) {
long long termino_actual = puntos_y[i] % MODULO;
long long numerador_prod = 1;
long long denominador_prod = 1;
// Cálculo del producto para el i-ésimo término
for (int j = 1; j <= cantidad_puntos; ++j) {
if (i == j) continue;
// (valor_a_evaluar - puntos_x[j])
numerador_prod = numerador_prod * ((valor_a_evaluar - puntos_x[j] + MODULO) % MODULO) % MODULO;
// (puntos_x[i] - puntos_x[j])
denominador_prod = denominador_prod * ((puntos_x[i] - puntos_x[j] + MODULO) % MODULO) % MODULO;
}
// Multiplicar por el inverso modular del denominador
termino_actual = termino_actual * numerador_prod % MODULO;
termino_actual = termino_actual * inverso_modular(denominador_prod) % MODULO;
// Sumar al resultado final
resultado_final = (resultado_final + termino_actual) % MODULO;
}
printf("%lld\n", resultado_final);
return 0;
}
Criba Lineal (Sieve)
La criba lineal (o criba de Euler) es un algoritmo para encontrar todos los números primos hasta un límite dado en tiempo lineal. Marca los números compuestos exactamente una vez por su factor primo más pequeño.
#include <vector>
const int MAX_NUM = 1000000 + 5;
bool es_compuesto[MAX_NUM]; // true si es compuesto, false si es primo o 0/1
std::vector<int> lista_primos; // Almacena los números primos encontrados
// Función para precalcular primos hasta 'limite_n'
void precalcular_primos(int limite_n) {
// Inicializar el arreglo de compuestos
memset(es_compuesto, false, sizeof(es_compuesto));
lista_primos.clear(); // Limpiar lista de primos
for (int i = 2; i <= limite_n; ++i) {
if (!es_compuesto[i]) { // Si 'i' no ha sido marcado, es primo
lista_primos.push_back(i);
}
// Marcar múltiplos de 'i' usando los primos ya encontrados
for (int p_idx = 0; p_idx < lista_primos.size(); ++p_idx) {
int p_actual = lista_primos[p_idx];
if ((long long)i * p_actual > limite_n) break; // Excede el límite
es_compuesto[i * p_actual] = true; // Marcar como compuesto
if (i % p_actual == 0) break; // Optimization: si p_actual es el factor primo más pequeño de i,
// entonces i * p_actual será marcado por p_actual y no por i
}
}
}
// Ejemplo de uso:
// int main() {
// precalcular_primos(100);
// for (int primo : lista_primos) {
// printf("%d ", primo);
// }
// printf("\n");
// return 0;
// }
Teorema Chino del Resto Extendido (EXCRT)
El Teorema Chino del Resto (CRT) se utiliza para resolver un sistema de congruencias lineales. Su versión extendida (EXCRT) puede manejar módulos que no son coprimos. Resuelve un sistema de la forma:
\[x \equiv a_1 \pmod{m_1}\] \[x \equiv a_2 \pmod{m_2}\] \[\dots\] \[x \equiv a_n \pmod{m_n}\]
#include <iostream>
#include <numeric> // Para std::gcd
#include <vector>
const int MAX_EQUATIONS = 100000 + 5;
long long residuos[MAX_EQUATIONS]; // a_i
long long modulos[MAX_EQUATIONS]; // m_i
int num_ecuaciones;
// Función de Euclides extendido: ax + by = gcd(a,b)
// Calcula x y y tal que a*x + b*y = gcd(a,b)
void euclides_extendido(long long a, long long b, long long &x, long long &y) {
if (b == 0) {
x = 1;
y = 0;
return;
}
euclides_extendido(b, a % b, y, x);
y -= (a / b) * x;
}
// Multiplicación modular segura para grandes números
// (x * y) % p sin desbordamiento de long long
long long multiplicacion_modular_segura(long long x, long long y, long long p) {
long long res = 0;
x %= p;
while (y > 0) {
if (y & 1) res = (res + x) % p;
x = (x + x) % p;
y >>= 1;
}
return res;
}
// Mínimo común múltiplo (MCM) para long long
long long calcular_mcm(long long a, long long b) {
if (a == 0 || b == 0) return 0; // MCM con 0 es 0
return std::abs(a * b) / std::gcd(a, b);
}
// Resuelve el sistema de congruencias usando el Teorema Chino del Resto Extendido
long long resolver_excrt() {
long long sol_x = residuos[1]; // Solución actual
long long sol_modulo_m = modulos[1]; // Módulo acumulado (LCM de los módulos)
for (int i = 2; i <= num_ecuaciones; ++i) {
long long a_i = residuos[i];
long long m_i = modulos[i];
long long diff = (a_i - sol_x % m_i + m_i) % m_i; // (a_i - sol_x) mod m_i
long long g = std::gcd(sol_modulo_m, m_i);
if (diff % g != 0) {
return -1; // No hay solución
}
long long k_val, temp_y;
euclides_extendido(sol_modulo_m, m_i, k_val, temp_y); // sol_modulo_m * k_val + m_i * temp_y = g
// k_val = k_val * (diff / g) % (m_i / g)
k_val = multiplicacion_modular_segura(k_val, diff / g, m_i / g);
k_val = (k_val + (m_i / g)) % (m_i / g); // Asegurar k_val sea positivo
sol_x = sol_x + multiplicacion_modular_segura(k_val, sol_modulo_m, sol_modulo_m * (m_i / g));
sol_modulo_m = calcular_mcm(sol_modulo_m, m_i); // Nuevo módulo acumulado
sol_x = (sol_x % sol_modulo_m + sol_modulo_m) % sol_modulo_m; // Normalizar x
}
return sol_x;
}
// Función para lectura rápida de enteros
long long leer_long_largo() {
long long val = 0;
int signo = 1;
char c = getchar();
while (c < '0' || c > '9') {
if (c == '-') signo = -1;
c = getchar();
}
while (c >= '0' && c <= '9') {
val = (val << 1) + (val << 3) + c - '0';
c = getchar();
}
return val * signo;
}
int main() {
num_ecuaciones = leer_long_largo();
for (int i = 1; i <= num_ecuaciones; ++i) {
modulos[i] = leer_long_largo();
residuos[i] = leer_long_largo();
}
long long resultado = resolver_excrt();
printf("%lld\n", resultado);
return 0;
}
Eliminación Gaussiana
La eliminación gaussiana es un algoritmo para resolver sistemas de ecuaciones lineales, calcular la inversa de una matriz y determinar el rango de una matriz.
#include <iostream>
#include <vector>
#include <cmath> // Para fabs
#include <algorithm> // Para swap
#include <iomanip> // Para setprecision
const int MAX_DIM = 100 + 5;
double matriz_coeficientes[MAX_DIM][MAX_DIM]; // Matriz A
double vector_constantes[MAX_DIM]; // Vector B
int dimension_sistema;
// Función para lectura rápida de enteros
long long leer_long_largo() {
long long val = 0;
int signo = 1;
char c = getchar();
while (c < '0' || c > '9') {
if (c == '-') signo = -1;
c = getchar();
}
while (c >= '0' && c <= '9') {
val = (val << 1) + (val << 3) + c - '0';
c = getchar();
}
return val * signo;
}
int main() {
dimension_sistema = leer_long_largo();
for (int i = 1; i <= dimension_sistema; ++i) {
for (int j = 1; j <= dimension_sistema; ++j) {
matriz_coeficientes[i][j] = leer_long_largo();
}
vector_constantes[i] = leer_long_largo();
}
// Proceso de Eliminación (Forma escalonada)
for (int col = 1; col <= dimension_sistema; ++col) {
int fila_pivote = col;
// Encontrar la fila con el pivote más grande en la columna actual (para estabilidad numérica)
for (int i = col + 1; i <= dimension_sistema; ++i) {
if (fabs(matriz_coeficientes[i][col]) > fabs(matriz_coeficientes[fila_pivote][col])) {
fila_pivote = i;
}
}
// Intercambiar la fila actual con la fila_pivote
for (int j = 1; j <= dimension_sistema; ++j) {
std::swap(matriz_coeficientes[col][j], matriz_coeficientes[fila_pivote][j]);
}
std::swap(vector_constantes[col], vector_constantes[fila_pivote]);
// Si el pivote es cercano a cero, puede que no haya solución única
if (fabs(matriz_coeficientes[col][col]) < 1e-8) {
printf("No Solution\n");
return 0; // Podría ser infinitas soluciones o ninguna
}
// Normalizar la fila pivote (hacer que el pivote sea 1)
double factor_normalizacion = matriz_coeficientes[col][col];
for (int j = col; j <= dimension_sistema; ++j) {
matriz_coeficientes[col][j] /= factor_normalizacion;
}
vector_constantes[col] /= factor_normalizacion;
// Eliminar otras entradas en la columna actual
for (int i = 1; i <= dimension_sistema; ++i) {
if (i == col) continue; // No eliminar la fila pivote con ella misma
double factor_eliminacion = matriz_coeficientes[i][col];
for (int j = col; j <= dimension_sistema; ++j) {
matriz_coeficientes[i][j] -= factor_eliminacion * matriz_coeficientes[col][j];
}
vector_constantes[i] -= factor_eliminacion * vector_constantes[col];
}
}
// Imprimir las soluciones
for (int i = 1; i <= dimension_sistema; ++i) {
printf("%.2lf\n", vector_constantes[i]);
}
return 0;
}
Teoría de Grafos
Algoritmo de Dijkstra para la Ruta Más Corta de Origen Único
Dijkstra encuentra el camino más corto desde un nodo fuente único a todos los demás nodos en un grafo con pesos de arista no negativos. Utiliza una cola de prioridad para explorar los nodos en orden de distancia creciente.
#include <iostream>
#include <vector>
#include <queue> // Para std::priority_queue
#include <limits> // Para std::numeric_limits
#include <cstring> // Para memset
const int MAX_NODOS = 200000 + 10;
const long long INF_DISTANCIA = std::numeric_limits<long long>::max();
// Definición de un par para almacenar {peso, destino}
// priority_queue es un max-heap por defecto, usamos greater<pair<...>> para min-heap
using ParDistancia = std::pair<long long, int>;
std::vector<ParDistancia> adj_list[MAX_NODOS]; // Lista de adyacencia: {destino, peso}
long long distancias[MAX_NODOS]; // distancias[i] = distancia mínima desde el origen a i
bool visitado[MAX_NODOS]; // visitado[i] = true si el nodo i ha sido finalizado
int num_nodos, num_aristas, nodo_inicial;
// Función para lectura rápida de enteros
long long leer_long_largo() {
long long val = 0;
int signo = 1;
char c = getchar();
while (c < '0' || c > '9') {
if (c == '-') signo = -1;
c = getchar();
}
while (c >= '0' && c <= '9') {
val = (val << 1) + (val << 3) + c - '0';
c = getchar();
}
return val * signo;
}
void algoritmo_dijkstra(int origen) {
// Inicializar distancias a infinito y nodos como no visitados
for (int i = 1; i <= num_nodos; ++i) {
distancias[i] = INF_DISTANCIA;
visitado[i] = false;
}
distancias[origen] = 0; // La distancia al nodo origen es 0
std::priority_queue<ParDistancia, std::vector<ParDistancia>, std::greater<ParDistancia>> pq;
pq.push({0, origen}); // Insertar el nodo origen en la cola de prioridad
while (!pq.empty()) {
long long d_actual = pq.top().first;
int u = pq.top().second;
pq.pop();
if (visitado[u]) continue; // Si ya procesamos este nodo, continuar
visitado[u] = true;
// Relajar las aristas salientes del nodo u
for (const auto& borde : adj_list[u]) {
int v = borde.first;
long long peso_uv = borde.second;
if (distancias[v] > distancias[u] + peso_uv) {
distancias[v] = distancias[u] + peso_uv;
pq.push({distancias[v], v});
}
}
}
}
int main() {
num_nodos = leer_long_largo();
num_aristas = leer_long_largo();
nodo_inicial = leer_long_largo();
for (int i = 0; i < num_aristas; ++i) {
int u = leer_long_largo();
int v = leer_long_largo();
long long peso = leer_long_largo();
adj_list[u].push_back({v, peso});
}
algoritmo_dijkstra(nodo_inicial);
for (int i = 1; i <= num_nodos; ++i) {
printf("%lld ", distancias[i]);
}
printf("\n");
return 0;
}
Camino Euleriano
Un camino Euleriano en un grafo es un camino que visita cada arista exactamente una vez. Un grafo tiene un camino Euleriano si es conexo y tiene como máximo dos vértices de grado impar (para grafos no dirigidos) o, para grafos diirgidos, como máximo un vértice con (grado_salida - grado_entrada = 1) y como máximo un vértice con (grado_entrada - grado_salida = 1), y todos los demás con grado_entrada = grado_salida.
#include <iostream>
#include <vector>
#include <algorithm> // Para std::sort
#include <stack> // Para std::stack (implícito en el DFS recursivo)
#include <cstdio> // Para getchar
const int MAX_VERTICES = 200000 + 10;
// Lista de adyacencia para el grafo dirigido. Los bordes están ordenados.
std::vector<int> adj[MAX_VERTICES];
int grados_entrada[MAX_VERTICES]; // Grado de entrada de cada vértice
// `ptr_adj[u]` se usa para saber cuál es la siguiente arista a visitar desde `u`
// Esto evita revisitar aristas en el DFS
int ptr_adj[MAX_VERTICES];
std::vector<int> camino_resultante; // El camino Euleriano resultante (en orden inverso)
int num_vertices_graph, num_aristas_graph;
// Función para lectura rápida de enteros
long long leer_long_largo() {
long long val = 0;
int signo = 1;
char c = getchar();
while (c < '0' || c > '9') {
if (c == '-') signo = -1;
c = c == ' '? getchar() : getchar(); // Saltar espacio si hay
}
while (c >= '0' && c <= '9') {
val = (val << 1) + (val << 3) + c - '0';
c = getchar();
}
return val * signo;
}
// DFS para encontrar el camino Euleriano
void encontrar_camino_euleriano_dfs(int u) {
// Itera sobre las aristas de u. `ptr_adj[u]` asegura que cada arista se visite una vez.
for (int& i = ptr_adj[u]; i < (int)adj[u].size(); ) {
int v = adj[u][i++]; // Obtener el siguiente vecino y avanzar el puntero
encontrar_camino_euleriano_dfs(v);
}
camino_resultante.push_back(u); // Añadir u al camino (se añade en orden inverso)
}
int main() {
num_vertices_graph = leer_long_largo();
num_aristas_graph = leer_long_largo();
for (int i = 0; i < num_aristas_graph; ++i) {
int u = leer_long_largo();
int v = leer_long_largo();
adj[u].push_back(v);
grados_entrada[v]++;
}
// Ordenar las listas de adyacencia para asegurar un orden lexicográfico si es necesario
for (int i = 1; i <= num_vertices_graph; ++i) {
std::sort(adj[i].begin(), adj[i].end());
}
int inicio_camino = 0; // Nodo donde comienza el camino Euleriano
int count_start_nodes = 0; // Contar nodos con (grado_salida - grado_entrada = 1)
int count_end_nodes = 0; // Contar nodos con (grado_entrada - grado_salida = 1)
// Determinar el nodo de inicio y verificar las condiciones del grafo
for (int i = 1; i <= num_vertices_graph; ++i) {
int grado_salida = adj[i].size();
if (grado_salida == grados_entrada[i] + 1) { // Nodo con una arista de salida 'extra'
count_start_nodes++;
inicio_camino = i;
} else if (grados_entrada[i] == grado_salida + 1) { // Nodo con una arista de entrada 'extra'
count_end_nodes++;
} else if (grado_salida != grados_entrada[i]) { // Si la diferencia es > 1, no hay camino Euleriano
printf("No\n");
return 0;
}
}
// Un camino Euleriano requiere:
// 1. O bien (0 nodos con grado_salida-grado_entrada=1 y 0 nodos con grado_entrada-grado_salida=1) -> Ciclo Euleriano
// 2. O bien (1 nodo con grado_salida-grado_entrada=1 y 1 nodo con grado_entrada-grado_salida=1) -> Camino Euleriano
if (!((count_start_nodes == 0 && count_end_nodes == 0) || (count_start_nodes == 1 && count_end_nodes == 1))) {
printf("No\n");
return 0;
}
// Si es un ciclo Euleriano, cualquier nodo puede ser el inicio. Escoger el primer nodo válido.
if (inicio_camino == 0) {
for (int i = 1; i <= num_vertices_graph; ++i) {
if (!adj[i].empty() || grados_entrada[i] > 0) { // Si el nodo tiene aristas
inicio_camino = i;
break;
}
}
if (inicio_camino == 0) { // Grafo vacío
if (num_aristas_graph == 0) {
// Si no hay aristas, y se buscan 0 aristas, es un camino válido.
// Aunque el problema pide N+1 nodos. Asumimos que si no hay aristas, no hay camino.
// A menos que N=1, M=0, en cuyo caso "1\n" sería el camino.
// Para este problema, asumimos que se espera algo más que un nodo aislado.
printf("No\n");
return 0;
}
}
}
// Si todavía no hay nodo de inicio, el grafo está vacío o solo contiene nodos aislados.
// Ocurre si todos los nodos tienen grado de salida y entrada 0, y no se encontró un inicio_camino.
// Esto significa que no hay aristas para formar un camino.
if (inicio_camino == 0 && num_aristas_graph > 0) {
printf("No\n");
return 0;
} else if (inicio_camino == 0 && num_aristas_graph == 0) {
// Caso de grafo con N nodos, 0 aristas. Si N=0, M=0, no hay camino.
// Si N>0, M=0, no hay camino Euleriano con aristas.
printf("No\n");
return 0;
}
encontrar_camino_euleriano_dfs(inicio_camino);
// Si el número de nodos en el camino no coincide con num_aristas_graph + 1
if (camino_resultante.size() != num_aristas_graph + 1) {
printf("No\n");
return 0;
}
// Imprimir el camino en el orden correcto (de último a primero)
for (int i = camino_resultante.size() - 1; i >= 0; --i) {
printf("%d ", camino_resultante[i]);
}
printf("\n");
return 0;
}
Reducción a Componentes Fuertemente Conectadas (SCC) con Tarjan
El algoritmo de Tarjan encuentra las componentes fuertemente conectadas (SCC) de un grafo dirigido. Una SCC es un subgrafo donde cada vértice es alcanzable desde cualquier otro vértice en ese subgrafo. Una vez identificadas, el grafo puede ser "condensado" en un grafo acíclico dirigido (DAG) de SCCs.
#include <iostream>
#include <vector>
#include <stack>
#include <algorithm> // Para std::max
#include <map> // Para evitar aristas duplicadas en el grafo condensado
#include <queue> // Para el topological sort
const int MAX_NODOS_SCC = 10000 + 10;
std::vector<int> adj_original[MAX_NODOS_SCC]; // Grafo original
int pesos_nodo_original[MAX_NODOS_SCC]; // Pesos asociados a cada nodo
// Variables para el algoritmo de Tarjan
int tiempo_descubrimiento[MAX_NODOS_SCC]; // dfn
int tiempo_min_alcanzable[MAX_NODOS_SCC]; // low
std::stack<int> pila_nodos_tarjan;
bool en_pila[MAX_NODOS_SCC]; // Indica si un nodo está en la pila
int id_componente[MAX_NODOS_SCC]; // id_componente[u] = ID de la SCC a la que pertenece u
int contador_tiempo; // Contador global de tiempo
int num_scc; // Número total de SCCs
int suma_pesos_scc[MAX_NODOS_SCC]; // Suma de pesos de los nodos en cada SCC
// DFS de Tarjan
void tarjan_dfs(int u) {
tiempo_descubrimiento[u] = tiempo_min_alcanzable[u] = ++contador_tiempo;
pila_nodos_tarjan.push(u);
en_pila[u] = true;
for (int v : adj_original[u]) {
if (!tiempo_descubrimiento[v]) { // Si v no ha sido visitado
tarjan_dfs(v);
tiempo_min_alcanzable[u] = std::min(tiempo_min_alcanzable[u], tiempo_min_alcanzable[v]);
} else if (en_pila[v]) { // Si v está en la pila (arista de retroceso)
tiempo_min_alcanzable[u] = std::min(tiempo_min_alcanzable[u], tiempo_descubrimiento[v]);
}
}
// Si u es la raíz de una SCC
if (tiempo_descubrimiento[u] == tiempo_min_alcanzable[u]) {
num_scc++;
int nodo_actual;
do {
nodo_actual = pila_nodos_tarjan.top();
pila_nodos_tarjan.pop();
en_pila[nodo_actual] = false;
id_componente[nodo_actual] = num_scc;
suma_pesos_scc[num_scc] += pesos_nodo_original[nodo_actual];
} while (nodo_actual != u);
}
}
// Grafo condensado (DAG de SCCs)
std::vector<int> adj_scc[MAX_NODOS_SCC];
int grados_entrada_scc[MAX_NODOS_SCC]; // Grados de entrada para el DAG
long long dp_scc[MAX_NODOS_SCC]; // DP para la suma máxima de pesos en el DAG
// Map para evitar añadir aristas duplicadas en el grafo condensado
std::map<std::pair<int, int>, bool> arista_ya_agregada;
// Algoritmo de TopSort para calcular la suma máxima en el DAG
void topological_sort_dp() {
std::queue<int> q_topological;
long long max_suma_total = 0;
// Inicializar la cola con SCCs sin dependencias (grado de entrada 0)
for (int i = 1; i <= num_scc; ++i) {
if (grados_entrada_scc[i] == 0) {
q_topological.push(i);
dp_scc[i] = suma_pesos_scc[i]; // La DP inicial es la suma de sus propios pesos
}
}
while (!q_topological.empty()) {
int actual_scc = q_topological.front();
q_topological.pop();
max_suma_total = std::max(max_suma_total, dp_scc[actual_scc]); // Actualizar la suma máxima global
for (int siguiente_scc : adj_scc[actual_scc]) {
dp_scc[siguiente_scc] = std::max(dp_scc[siguiente_scc], dp_scc[actual_scc] + suma_pesos_scc[siguiente_scc]);
grados_entrada_scc[siguiente_scc]--;
if (grados_entrada_scc[siguiente_scc] == 0) {
q_topological.push(siguiente_scc);
}
}
}
printf("%lld\n", max_suma_total);
}
// Función para lectura rápida de enteros
long long leer_long_largo() {
long long val = 0;
int signo = 1;
char c = getchar();
while (c < '0' || c > '9') {
if (c == '-') signo = -1;
c = getchar();
}
while (c >= '0' && c <= '9') {
val = (val << 1) + (val << 3) + c - '0';
c = getchar();
}
return val * signo;
}
int main() {
int n_nodos = leer_long_largo();
int m_aristas = leer_long_largo();
for (int i = 1; i <= n_nodos; ++i) {
pesos_nodo_original[i] = leer_long_largo();
}
for (int i = 0; i < m_aristas; ++i) {
int u = leer_long_largo();
int v = leer_long_largo();
adj_original[u].push_back(v);
}
// Ejecutar Tarjan en todos los nodos no visitados
for (int i = 1; i <= n_nodos; ++i) {
if (!tiempo_descubrimiento[i]) {
tarjan_dfs(i);
}
}
// Construir el grafo condensado (DAG de SCCs)
for (int u = 1; u <= n_nodos; ++u) {
for (int v : adj_original[u]) {
int scc_u = id_componente[u];
int scc_v = id_componente[v];
if (scc_u != scc_v) { // Si están en diferentes SCCs, añadir una arista en el DAG
if (!arista_ya_agregada[{scc_u, scc_v}]) {
adj_scc[scc_u].push_back(scc_v);
grados_entrada_scc[scc_v]++;
arista_ya_agregada[{scc_u, scc_v}] = true;
}
}
}
}
// Inicializar dp_scc con 0 para asegurar el correcto cálculo del max
for (int i = 1; i <= num_scc; ++i) {
dp_scc[i] = 0;
}
topological_sort_dp(); // Calcular la suma máxima de pesos
return 0;
}
Componentes Doblemente Conectadas por Vértices (v-BCC)
Las componentes doblemente conectadas por vértices (v-BCC) son subgrafos máximos tales que la eliminación de cualquier vértice no desconecta el subgrafo. El algoritmo de Tarjan se puede adaptar para encontrarlas, identificando puntos de articulación y gestionando una pila de aristas/vértices.
#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>
const int MAX_NODOS_BCC = 10000 + 5;
std::vector<int> adj_lista[MAX_NODOS_BCC]; // Lista de adyacencia
int tiempo_descub[MAX_NODOS_BCC]; // dfn
int tiempo_bajo_link[MAX_NODOS_BCC]; // low
int contador_tiempo_global;
std::stack<int> pila_vertices_bcc; // Pila de vértices para construir BCCs
std::vector<std::vector<int>> componentes_bcc; // Almacena las v-BCCs
// Función para lectura rápida de enteros
long long leer_long_largo() {
long long val = 0;
int signo = 1;
char c = getchar();
while (c < '0' || c > '9') {
if (c == '-') signo = -1;
c = getchar();
}
while (c >= '0' && c <= '9') {
val = (val << 1) + (val << 3) + c - '0';
c = getchar();
}
return val * signo;
}
// DFS para encontrar v-BCCs
void tarjan_bcc_dfs(int u, int padre) {
tiempo_descub[u] = tiempo_bajo_link[u] = ++contador_tiempo_global;
pila_vertices_bcc.push(u);
int hijos_dfs = 0; // Número de hijos en el árbol DFS
for (int v : adj_lista[u]) {
if (v == padre) continue; // Ignorar el borde hacia el padre en el árbol DFS
if (tiempo_descub[v]) { // v ya ha sido visitado
tiempo_bajo_link[u] = std::min(tiempo_bajo_link[u], tiempo_descub[v]);
} else { // v no ha sido visitado
tarjan_bcc_dfs(v, u);
tiempo_bajo_link[u] = std::min(tiempo_bajo_link[u], tiempo_bajo_link[v]);
hijos_dfs++;
// Si u es un punto de articulación y v-BCC
if (tiempo_bajo_link[v] >= tiempo_descub[u]) {
// Nuevo BCC encontrado
componentes_bcc.emplace_back();
int nodo_en_pila;
do {
nodo_en_pila = pila_vertices_bcc.top();
pila_vertices_bcc.pop();
componentes_bcc.back().push_back(nodo_en_pila);
} while (nodo_en_pila != v);
componentes_bcc.back().push_back(u); // u es parte de esta BCC
}
}
}
// Caso especial: la raíz del DFS es un punto de articulación si tiene más de un hijo en el árbol DFS
// (ya manejado por el if de arriba si el padre es 0)
// Pero si u es la raíz del DFS y no tiene padre, y tiene solo un hijo, no es punto de articulación.
// En este problema, la condición es `dfn[x] <= low[y]`, que cubre este caso
// para cualquier nodo 'x' con un hijo 'y'.
// Si la pila no está vacía al final, la última BCC contiene los nodos restantes.
}
int main() {
// Ejemplo de uso:
// int n_nodes = leer_long_largo();
// int m_edges = leer_long_largo();
// for (int i = 0; i < m_edges; ++i) {
// int u = leer_long_largo(), v = leer_long_largo();
// adj_lista[u].push_back(v);
// adj_lista[v].push_back(u); // Grafo no dirigido
// }
// Para un grafo no dirigido con n_nodes vértices
// for (int i = 1; i <= n_nodes; ++i) {
// if (!tiempo_descub[i]) {
// tarjan_bcc_dfs(i, 0); // 0 indica sin padre para la raíz del DFS
// }
// }
// Si hay elementos restantes en la pila (para el caso de un grafo conexo que es una única BCC)
// Esto es un detalle del manejo del código original que implica que hay aristas
// en la pila, no vértices. El snippet original es para v-BCC a partir de aristas.
// El código reescrito es para v-BCC de vértices.
// Para el snippet original que usaba `st[++top] = x` como "aristas", una pila de vértices
// con un poco más de lógica al "pop" es lo que se espera para construir las BCCs de vértices.
// La implementación de arriba devuelve los vértices en cada BCC.
// Nota: El snippet original es muy fragmentado. Esta es una implementación
// completa de Tarjan para encontrar v-BCCs (componentes doblemente conectadas
// por vértices), no aristas.
// El resultado sería en `componentes_bcc`.
// Por ejemplo, para imprimir las BCCs:
// for (const auto& bcc : componentes_bcc) {
// for (int v : bcc) {
// std::cout << v << " ";
// }
// std::cout << std::endl;
// }
// El snippet original parecía ser una adaptación para BCCs de aristas,
// donde la pila almacenaba vértices y al encontrar un puente se sacaban
// los vértices hasta el "hijo" del punto de articulación.
// La versión de arriba es más estándar para v-BCCs (puntos de articulación).
// Si el gráfico es conexo y el DFS no abarca todos los vértices, significa que
// hay varios componentes desconectados, y tarjan_bcc_dfs debe llamarse para
// cada nodo no visitado. Si una BCC es solo un nodo aislado, también se puede añadir.
// El código original maneja el caso de un nodo aislado al principio:
// `if(x == root && !hd[x])ans[++num].push_back(x);`
// Para imitar esto, después del bucle principal, si quedan nodos aislados o no visitados:
// Por simplicidad, se puede asumir que el problema original busca v-BCCs en un grafo conexo.
// Si el grafo es disconexo, simplemente llamar a `tarjan_bcc_dfs` para cada nodo no visitado.
printf("// La implementación de Tarjan para v-BCCs se muestra arriba. Se necesita un grafo completo para ejecutar.\n");
printf("// El fragmento original era una plantilla y carecía de contexto completo de las estructuras de datos.\n");
printf("// Esta implementación sigue la lógica estándar de Tarjan para encontrar puntos de articulación y BCCs.\n");
return 0;
}
Estructuras de Datos
Cola Monótona
Una cola monótona (o deque monótona) es una estructura de datos que mantiene sus elementos en orden monótono (creciente o decreciente). Es ideal para problemas de ventana deslizante donde se necesita el mínimo o máximo en un rango.
#include <iostream>
#include <vector>
#include <deque> // Para std::deque
#include <cstdio> // Para printf
const int MAX_ARRAY_SIZE = 1000000 + 10;
int arreglo_principal[MAX_ARRAY_SIZE];
std::deque<int> cola_monotonica; // Almacena índices de los elementos
int n_elementos, tamano_ventana;
// Función para lectura rápida de enteros
long long leer_long_largo() {
long long val = 0;
int signo = 1;
char c = getchar();
while (c < '0' || c > '9') {
if (c == '-') signo = -1;
c = getchar();
}
while (c >= '0' && c <= '9') {
val = (val << 1) + (val << 3) + c - '0';
c = getchar();
}
return val * signo;
}
int main() {
n_elementos = leer_long_largo();
tamano_ventana = leer_long_largo();
for (int i = 1; i <= n_elementos; ++i) {
arreglo_principal[i] = leer_long_largo();
}
// Calcular el mínimo en cada ventana deslizante
cola_monotonica.clear(); // Limpiar la cola para el primer cálculo
for (int i = 1; i <= n_elementos; ++i) {
// Eliminar elementos del frente que están fuera de la ventana actual
while (!cola_monotonica.empty() && cola_monotonica.front() <= i - tamano_ventana) {
cola_monotonica.pop_front();
}
// Eliminar elementos de la parte trasera que son mayores o iguales al actual
// (porque el actual es más pequeño y está más a la derecha, por lo tanto, es mejor candidato para el mínimo)
while (!cola_monotonica.empty() && arreglo_principal[i] <= arreglo_principal[cola_monotonica.back()]) {
cola_monotonica.pop_back();
}
cola_monotonica.push_back(i); // Añadir el índice actual a la cola
// Una vez que la ventana tiene el tamaño completo, imprimir el mínimo
if (i >= tamano_ventana) {
printf("%d ", arreglo_principal[cola_monotonica.front()]);
}
}
printf("\n");
// Calcular el máximo en cada ventana deslizante
cola_monotonica.clear(); // Limpiar la cola para el segundo cálculo
for (int i = 1; i <= n_elementos; ++i) {
// Eliminar elementos del frente que están fuera de la ventana actual
while (!cola_monotonica.empty() && cola_monotonica.front() <= i - tamano_ventana) {
cola_monotonica.pop_front();
}
// Eliminar elementos de la parte trasera que son menores o iguales al actual
// (porque el actual es más grande y está más a la derecha, por lo tanto, es mejor candidato para el máximo)
while (!cola_monotonica.empty() && arreglo_principal[i] >= arreglo_principal[cola_monotonica.back()]) {
cola_monotonica.pop_back();
}
cola_monotonica.push_back(i); // Añadir el índice actual a la cola
// Una vez que la ventana tiene el tamaño completo, imprimir el máximo
if (i >= tamano_ventana) {
printf("%d ", arreglo_principal[cola_monotonica.front()]);
}
}
printf("\n");
return 0;
}
Tabla ST (Sparse Table)
Una tabla ST es una estructura de datos estática que puede responder consultas de mínimo o máximo en un rango (RMQ) en tiempo \(O(1)\) después de una preprocesamiento en \(O(N \log N)\). Es útil cuando los valores del arreglo no cambian.
#include <iostream>
#include <vector>
#include <cmath> // Para log2
#include <algorithm> // Para max
#include <cstdio> // Para printf
const int MAX_ST_SIZE = 100000 + 10;
const int MAX_LOG_N = 20; // log2(10^5) approx 16-17, so 20 is safe
int datos_array[MAX_ST_SIZE];
int st_table[MAX_ST_SIZE][MAX_LOG_N + 1]; // st_table[i][j] = max en rango [i, i + 2^j - 1]
// Función para lectura rápida de enteros
long long leer_long_largo() {
long long val = 0;
int signo = 1;
char c = getchar();
while (c < '0' || c > '9') {
if (c == '-') signo = -1;
c = getchar();
}
while (c >= '0' && c <= '9') {
val = (val << 1) + (val << 3) + c - '0';
c = getchar();
}
return val * signo;
}
int main() {
int n_elementos = leer_long_largo();
int q_consultas = leer_long_largo();
// Llenar el array y la primera columna de la ST table
for (int i = 1; i <= n_elementos; ++i) {
datos_array[i] = leer_long_largo();
st_table[i][0] = datos_array[i];
}
// Preprocesamiento de la tabla ST
// j es la potencia de 2 (longitud del rango 2^j)
for (int j = 1; j <= MAX_LOG_N; ++j) {
// i es el inicio del rango
// i + (1 << j) - 1 es el final del rango
for (int i = 1; i + (1 << j) - 1 <= n_elementos; ++i) {
// El rango [i, i + 2^j - 1] se divide en dos rangos de 2^(j-1)
// [i, i + 2^(j-1) - 1] y [i + 2^(j-1), i + 2^j - 1]
st_table[i][j] = std::max(st_table[i][j - 1], st_table[i + (1 << (j - 1))][j - 1]);
}
}
// Procesar consultas
for (int k = 0; k < q_consultas; ++k) {
int l = leer_long_largo(); // Inicio del rango de consulta
int r = leer_long_largo(); // Fin del rango de consulta
// Calcular p = log2(longitud del rango)
int longitud_rango = r - l + 1;
int p = std::log2(longitud_rango);
// La respuesta es el máximo de dos rangos de longitud 2^p
// [l, l + 2^p - 1] y [r - 2^p + 1, r]
printf("%d\n", std::max(st_table[l][p], st_table[r - (1 << p) + 1][p]));
}
return 0;
}
Árbol de Segmentos con Propagación Lazy
Un árbol de segmentos es una estructura de datos versátil para consultar y actualizar rangos en un arreglo. Esta versión incluye propagación lazy para manejar eficientemente tanto operaciones de multiplicación como de adición en rangos.
#include <iostream>
#include <vector>
#include <cstdio> // Para getchar
const int MAX_SEGMENT_TREE_NODES = 100000 + 10; // Tamaño N
const int TREE_ARRAY_SIZE = MAX_SEGMENT_TREE_NODES << 2; // ~4*N para el árbol
long long arreglo_inicial[MAX_SEGMENT_TREE_NODES];
int num_elementos, num_consultas;
long long modulo_val;
// Estructura para el nodo del Segment Tree
struct SegmentTreeNode {
long long suma; // Suma del rango cubierto por el nodo
long long lazy_mult; // Multiplicador lazy
long long lazy_add; // Sumador lazy
SegmentTreeNode() : suma(0), lazy_mult(1), lazy_add(0) {} // Constructor por defecto
};
SegmentTreeNode arbol_segmentos[TREE_ARRAY_SIZE];
// Función para actualizar la suma de un nodo basándose en sus hijos
void push_up(int nodo_idx) {
arbol_segmentos[nodo_idx].suma = (arbol_segmentos[nodo_idx << 1].suma + arbol_segmentos[nodo_idx << 1 | 1].suma) % modulo_val;
}
// Aplica una operación lazy (multiplicación y adición) a un nodo
void aplicar_lazy(int nodo_idx, long long mult_val, long long add_val, int rango_len) {
arbol_segmentos[nodo_idx].suma = (arbol_segmentos[nodo_idx].suma * mult_val % modulo_val + add_val * rango_len % modulo_val) % modulo_val;
arbol_segmentos[nodo_idx].lazy_mult = arbol_segmentos[nodo_idx].lazy_mult * mult_val % modulo_val;
arbol_segmentos[nodo_idx].lazy_add = (arbol_segmentos[nodo_idx].lazy_add * mult_val % modulo_val + add_val) % modulo_val;
}
// Propaga las operaciones lazy a los hijos de un nodo
void push_down(int nodo_idx, int rango_izq, int rango_der) {
if (arbol_segmentos[nodo_idx].lazy_mult == 1 && arbol_segmentos[nodo_idx].lazy_add == 0) {
return; // No hay operaciones lazy pendientes
}
int mid = rango_izq + (rango_der - rango_izq) / 2;
int len_izq = mid - rango_izq + 1;
int len_der = rango_der - mid;
// Propagar al hijo izquierdo
aplicar_lazy(nodo_idx << 1, arbol_segmentos[nodo_idx].lazy_mult, arbol_segmentos[nodo_idx].lazy_add, len_izq);
// Propagar al hijo derecho
aplicar_lazy(nodo_idx << 1 | 1, arbol_segmentos[nodo_idx].lazy_mult, arbol_segmentos[nodo_idx].lazy_add, len_der);
// Resetear lazy tags del nodo actual
arbol_segmentos[nodo_idx].lazy_mult = 1;
arbol_segmentos[nodo_idx].lazy_add = 0;
}
// Construye el Segment Tree
void construir(int nodo_idx, int rango_izq, int rango_der) {
if (rango_izq == rango_der) {
arbol_segmentos[nodo_idx].suma = arreglo_inicial[rango_izq] % modulo_val;
return;
}
int mid = rango_izq + (rango_der - rango_izq) / 2;
construir(nodo_idx << 1, rango_izq, mid);
construir(nodo_idx << 1 | 1, mid + 1, rango_der);
push_up(nodo_idx);
}
// Modifica un rango con multiplicación
void modificar_multiplicacion(int nodo_idx, int rango_izq, int rango_der, int query_izq, int query_der, long long valor_mult) {
if (query_izq <= rango_izq && rango_der <= query_der) {
aplicar_lazy(nodo_idx, valor_mult, 0, rango_der - rango_izq + 1);
return;
}
push_down(nodo_idx, rango_izq, rango_der); // Propagar antes de dividir
int mid = rango_izq + (rango_der - rango_izq) / 2;
if (query_izq <= mid) {
modificar_multiplicacion(nodo_idx << 1, rango_izq, mid, query_izq, query_der, valor_mult);
}
if (query_der > mid) {
modificar_multiplicacion(nodo_idx << 1 | 1, mid + 1, rango_der, query_izq, query_der, valor_mult);
}
push_up(nodo_idx);
}
// Modifica un rango con adición
void modificar_adicion(int nodo_idx, int rango_izq, int rango_der, int query_izq, int query_der, long long valor_add) {
if (query_izq <= rango_izq && rango_der <= query_der) {
aplicar_lazy(nodo_idx, 1, valor_add, rango_der - rango_izq + 1);
return;
}
push_down(nodo_idx, rango_izq, rango_der); // Propagar antes de dividir
int mid = rango_izq + (rango_der - rango_izq) / 2;
if (query_izq <= mid) {
modificar_adicion(nodo_idx << 1, rango_izq, mid, query_izq, query_der, valor_add);
}
if (query_der > mid) {
modificar_adicion(nodo_idx << 1 | 1, mid + 1, rango_der, query_izq, query_der, valor_add);
}
push_up(nodo_idx);
}
// Consulta la suma de un rango
long long consultar_rango(int nodo_idx, int rango_izq, int rango_der, int query_izq, int query_der) {
// Si el rango de la consulta está fuera del rango actual
if (query_izq > rango_der || query_der < rango_izq) {
return 0;
}
// Si el rango del nodo actual está completamente dentro del rango de la consulta
if (query_izq <= rango_izq && rango_der <= query_der) {
return arbol_segmentos[nodo_idx].suma;
}
push_down(nodo_idx, rango_izq, rango_der); // Propagar antes de dividir
int mid = rango_izq + (rango_der - rango_izq) / 2;
long long suma_izq = consultar_rango(nodo_idx << 1, rango_izq, mid, query_izq, query_der);
long long suma_der = consultar_rango(nodo_idx << 1 | 1, mid + 1, rango_der, query_izq, query_der);
return (suma_izq + suma_der) % modulo_val;
}
// Función para lectura rápida de enteros
long long leer_long_largo() {
long long val = 0;
int signo = 1;
char c = getchar();
while (c < '0' || c > '9') {
if (c == '-') signo = -1;
c = getchar();
}
while (c >= '0' && c <= '9') {
val = (val << 1) + (val << 3) + c - '0';
c = getchar();
}
return val * signo;
}
int main() {
num_elementos = leer_long_largo();
num_consultas = leer_long_largo();
modulo_val = leer_long_largo();
for (int i = 1; i <= num_elementos; ++i) {
arreglo_inicial[i] = leer_long_largo();
}
construir(1, 1, num_elementos); // Construir el árbol desde la raíz (nodo 1)
for (int i = 0; i < num_consultas; ++i) {
int tipo_op = leer_long_largo();
int l = leer_long_largo();
int r = leer_long_largo();
if (tipo_op == 1) { // Operación de multiplicación en rango
long long k = leer_long_largo();
modificar_multiplicacion(1, 1, num_elementos, l, r, k);
} else if (tipo_op == 2) { // Operación de adición en rango
long long k = leer_long_largo();
modificar_adicion(1, 1, num_elementos, l, r, k);
} else { // Consulta de suma en rango
printf("%lld\n", consultar_rango(1, 1, num_elementos, l, r));
}
}
return 0;
}
Árbol de Prefijos (Trie)
Un Trie (árbol de prefijos) es una estructura de datos basada en árboles, utilizada para almacenar una colección de cadenas donde las claves son típicamente cadenas. Es eficiente para buscar prefijos y contar palabras con prefijos comunes.
#include <iostream>
#include <string>
#include <vector>
#include <cstring> // Para strlen, memset
#include <map> // Podría usarse para mapear caracteres, pero aquí se usa un array fijo
#include <cstdio> // Para scanf/printf
const int MAX_NODOS_TRIE = 3000000 + 5; // Suficientemente grande para el total de caracteres
const int ALPHABET_SIZE = 62; // 26 minúsculas + 26 mayúsculas + 10 dígitos
// trie_nodes[nodo_idx][char_idx] = índice del siguiente nodo
int trie_nodes[MAX_NODOS_TRIE][ALPHABET_SIZE];
int count_prefixes[MAX_NODOS_TRIE]; // Cuántas palabras pasan por este nodo (o terminan aquí)
int total_nodes_trie; // Contador para nuevos nodos
char input_buffer[MAX_NODOS_TRIE]; // Buffer para leer cadenas
// Función para mapear un carácter a un índice numérico
int map_char_to_index(char c) {
if (c >= 'a' && c <= 'z') return c - 'a';
if (c >= '0' && c <= '9') return 26 + (c - '0');
if (c >= 'A' && c <= 'Z') return 36 + (c - 'A');
return -1; // Carácter no válido
}
// Inserta una cadena en el Trie
void insert_string(const char* str) {
int current_node = 0; // Raíz del Trie
int len = strlen(str);
for (int i = 0; i < len; ++i) {
int char_index = map_char_to_index(str[i]);
if (char_index == -1) continue; // Ignorar caracteres no válidos
if (!trie_nodes[current_node][char_index]) {
trie_nodes[current_node][char_index] = ++total_nodes_trie;
}
current_node = trie_nodes[current_node][char_index];
count_prefixes[current_node]++; // Incrementar el contador de prefijos
}
}
// Consulta cuántas cadenas insertadas tienen un prefijo dado
long long query_prefix_count(const char* str) {
int current_node = 0; // Raíz del Trie
int len = strlen(str);
for (int i = 0; i < len; ++i) {
int char_index = map_char_to_index(str[i]);
if (char_index == -1) return 0; // Prefijo contiene carácter no válido, no hay coincidencias
if (!trie_nodes[current_node][char_index]) {
return 0; // No existe este prefijo
}
current_node = trie_nodes[current_node][char_index];
}
return count_prefixes[current_node]; // Número de palabras que tienen este prefijo
}
// Función para inicializar el Trie para un nuevo caso de prueba
void reset_trie() {
// Es más eficiente simplemente poner total_nodes_trie a 0 y
// reconstruir, si los nodos no se reutilizan.
// O limpiar los rangos de memoria usados:
for(int i = 0; i <= total_nodes_trie; ++i) {
memset(trie_nodes[i], 0, sizeof(trie_nodes[i]));
count_prefixes[i] = 0;
}
total_nodes_trie = 0; // La raíz es el nodo 0
}
// Función para lectura rápida de enteros
long long leer_long_largo() {
long long val = 0;
int signo = 1;
char c = getchar();
while (c < '0' || c > '9') {
if (c == '-') signo = -1;
c = getchar();
}
while (c >= '0' && c <= '9') {
val = (val << 1) + (val << 3) + c - '0';
c = getchar();
}
return val * signo;
}
// Función para resolver un caso de prueba
void solve_test_case() {
reset_trie(); // Resetear el Trie para cada caso
int n_words = leer_long_largo();
int q_queries = leer_long_largo();
for (int i = 0; i < n_words; ++i) {
scanf("%s", input_buffer);
insert_string(input_buffer);
}
for (int i = 0; i < q_queries; ++i) {
scanf("%s", input_buffer);
printf("%lld\n", query_prefix_count(input_buffer));
}
}
int main() {
// Si hay múltiples casos de prueba, llamar a solve_test_case() en un bucle
// int num_test_cases = leer_long_largo();
// while(num_test_cases--) {
// solve_test_case();
// }
// Asumiendo un único caso de prueba como en el original
solve_test_case();
return 0;
}
Árbol de Li Chao
Un árbol de Li Chao es una estructura de datos eficiente, a menudo implementada sobre un árbol de segmentos, que permite agregar líneas y consultar la línea con el valor máximo (o mínimo) en un punto dado \(x\). Es particularmente útil para problemas de programación dinámica con optimización de la envolvente convexa.
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath> // Para fabs
#include <limits> // Para numeric_limits
const int MAX_COORD_RANGE = 100000 + 5; // Máximo rango de coordenadas para el árbol
const double EPSILON_LCHAO = 1e-9; // Pequeña constante para comparaciones de punto flotante
const double INF_NEG_LCHAO = -std::numeric_limits<double>::infinity(); // Valor infinito negativo
// Estructura para representar una línea y su ID
struct Line {
double pendiente, intercepto_y;
int id_linea;
// Constructor por defecto para líneas "vacías"
Line() : pendiente(0), intercepto_y(INF_NEG_LCHAO), id_linea(0) {}
Line(double m, double b, int id) : pendiente(m), intercepto_y(b), id_linea(id) {}
// Calcula el valor de la línea en un punto x
double evaluar(int x_coord) const {
return pendiente * x_coord + intercepto_y;
}
};
// Comparador para decidir qué línea es "mejor" en un punto dado
// Devuelve true si linea_a es mejor que linea_b en x_coord
bool es_mejor_linea(const Line& linea_a, const Line& linea_b, int x_coord) {
if (linea_a.id_linea == 0) return false; // Si linea_a es vacía, no es mejor
if (linea_b.id_linea == 0) return true; // Si linea_b es vacía, linea_a es mejor
double val_a = linea_a.evaluar(x_coord);
double val_b = linea_b.evaluar(x_coord);
if (fabs(val_a - val_b) < EPSILON_LCHAO) {
return linea_a.id_linea < linea_b.id_linea; // Desempate por ID
}
return val_a > val_b; // Mayor valor es mejor
}
// Estructura del Árbol de Li Chao
struct LiChaoTree {
Line tree_lines[MAX_COORD_RANGE * 4]; // Cada nodo almacena la "línea dominante"
// Inserta o actualiza una línea en un segmento del árbol
// `current_node`: índice del nodo actual en el árbol
// `range_low`, `range_high`: rango de coordenadas que cubre el nodo actual
// `new_line`: la línea a insertar
void actualizar_linea(int current_node, int range_low, int range_high, Line new_line) {
int mid = range_low + (range_high - range_low) / 2;
Line& dominant_line = tree_lines[current_node];
// Comparar la nueva línea con la línea dominante en el punto medio
bool new_is_better_mid = es_mejor_linea(new_line, dominant_line, mid);
// Comparar la nueva línea con la línea dominante en el extremo izquierdo
bool new_is_better_low = es_mejor_linea(new_line, dominant_line, range_low);
if (new_is_better_mid) {
std::swap(new_line, dominant_line); // La nueva línea es mejor en el medio, se convierte en dominante
}
// Si el segmento es un punto único, no hay más subdivisiones
if (range_low == range_high) return;
// Si la nueva línea aún es mejor en el extremo izquierdo,
// o la línea antigua era mejor en el medio pero la nueva es mejor en el izquierdo
if (new_is_better_low != es_mejor_linea(new_line, dominant_line, range_low)) {
// Las líneas se cruzan en la mitad izquierda
actualizar_linea(current_node * 2, range_low, mid, new_line);
} else {
// Las líneas se cruzan en la mitad derecha
actualizar_linea(current_node * 2 + 1, mid + 1, range_high, new_line);
}
}
// Consulta la línea con el valor máximo en un punto x_query
// `current_node`: índice del nodo actual
// `range_low`, `range_high`: rango de coordenadas que cubre el nodo
// `x_query`: punto x para la consulta
Line consultar_punto(int current_node, int range_low, int range_high, int x_query) {
Line best_line = tree_lines[current_node]; // La línea dominante de este nodo
if (range_low == range_high) {
return best_line; // Nodo hoja, devuelve la línea dominante
}
int mid = range_low + (range_high - range_low) / 2;
if (x_query <= mid) {
best_line = es_mejor_linea(consultar_punto(current_node * 2, range_low, mid, x_query), best_line, x_query) ?
consultar_punto(current_node * 2, range_low, mid, x_query) : best_line;
} else {
best_line = es_mejor_linea(consultar_punto(current_node * 2 + 1, mid + 1, range_high, x_query), best_line, x_query) ?
consultar_punto(current_node * 2 + 1, mid + 1, range_high, x_query) : best_line;
}
return best_line;
}
};
LiChaoTree mi_li_chao_tree;
int N_ops;
long long last_ans = 0; // Para consultas dependientes de la última respuesta
int current_line_id = 0; // Contador de IDs para líneas
// Máximos valores para los parámetros del problema
int M1 = 100000; // Máximo valor para 'a' y 'c' (coordenadas x)
int M2 = 1000000000; // Máximo valor para 'b' y 'd' (coordenadas y)
int main() {
scanf("%d", &N_ops);
for (int i = 0; i < N_ops; ++i) {
int op_type, p1_x;
scanf("%d %d", &op_type, &p1_x);
p1_x = (p1_x + last_ans - 1) % M1 + 1; // Transformación para p1_x
if (op_type == 0) { // Consulta
Line result_line = mi_li_chao_tree.consultar_punto(1, 1, M1, p1_x);
printf("%d\n", result_line.id_linea);
last_ans = result_line.id_linea;
} else { // Inserción de línea
int p1_y, p2_x, p2_y;
scanf("%d %d %d", &p1_y, &p2_x, &p2_y);
p1_y = (p1_y + last_ans - 1) % M2 + 1;
p2_x = (p2_x + last_ans - 1) % M1 + 1;
p2_y = (p2_y + last_ans - 1) % M2 + 1;
if (p1_x > p2_x) { // Asegurarse de que p1_x <= p2_x
std::swap(p1_x, p2_x);
std::swap(p1_y, p2_y);
}
double m = 0, b = 0;
if (p1_x == p2_x) { // Línea vertical, tomar el máximo Y
m = 0; // Pendiente 0
b = std::max((double)p1_y, (double)p2_y);
} else {
m = (double)(p2_y - p1_y) / (p2_x - p1_x);
b = (double)p1_y - p1_x * m;
}
current_line_id++;
mi_li_chao_tree.actualizar_linea(1, 1, M1, Line(m, b, current_line_id));
}
}
return 0;
}
Treap FHQ (Árbol Binario de Búsqueda Balanceado)
Un Treap FHQ (también conocido como Treap sin rotaciones o Treap de Fuso) es una estructura de datos que combina las propiedades de un árbol binario de búsqueda y un heap. Mantiene el orden de los nodos por valor (propiedad BST) y por una prioridad aleatoria (propiedad heap), lo que lo convierte en un árbol balanceado. Es particularmente flexible para operaciones de rango como inserción, eliminación y reversión de segmentos.
#include <iostream>
#include <random> // Para std::mt19937, std::random_device
#include <algorithm> // Para std::swap
#include <vector> // Para std::vector
#include <ctime> // Para time(0) en seeding
const int MAX_NODOS_TREAP = 100000 + 10;
// Generador de números aleatorios para las prioridades del treap
std::mt19937 rng(time(0)); // Seed con el tiempo actual
struct TreapNode {
int valor; // Valor almacenado en el nodo
int prioridad; // Prioridad aleatoria (propiedad de heap)
int tamano; // Tamaño del subárbol
int hijo_izq, hijo_der; // Punteros a los hijos
bool lazy_invert; // Marca lazy para invertir subárbol
TreapNode() : valor(0), prioridad(0), tamano(0), hijo_izq(0), hijo_der(0), lazy_invert(false) {}
};
TreapNode treap_memoria[MAX_NODOS_TREAP];
int indice_proximo_nodo = 0; // Contador de nodos para asignar IDs
// Crea un nuevo nodo
int crear_nodo(int val) {
indice_proximo_nodo++;
treap_memoria[indice_proximo_nodo].valor = val;
treap_memoria[indice_proximo_nodo].prioridad = rng(); // Prioridad aleatoria
treap_memoria[indice_proximo_nodo].tamano = 1;
treap_memoria[indice_proximo_nodo].hijo_izq = 0;
treap_memoria[indice_proximo_nodo].hijo_der = 0;
treap_memoria[indice_proximo_nodo].lazy_invert = false;
return indice_proximo_nodo;
}
// Actualiza el tamaño de un nodo
void push_up(int nodo_idx) {
if (nodo_idx == 0) return;
treap_memoria[nodo_idx].tamano = treap_memoria[treap_memoria[nodo_idx].hijo_izq].tamano +
treap_memoria[treap_memoria[nodo_idx].hijo_der].tamano + 1;
}
// Propaga la marca lazy de inversión a los hijos
void push_down(int nodo_idx) {
if (nodo_idx == 0 || !treap_memoria[nodo_idx].lazy_invert) return;
// Intercambiar hijos y propagar la marca lazy
std::swap(treap_memoria[nodo_idx].hijo_izq, treap_memoria[nodo_idx].hijo_der);
if (treap_memoria[nodo_idx].hijo_izq != 0) {
treap_memoria[treap_memoria[nodo_idx].hijo_izq].lazy_invert ^= 1;
}
if (treap_memoria[nodo_idx].hijo_der != 0) {
treap_memoria[treap_memoria[nodo_idx].hijo_der].lazy_invert ^= 1;
}
treap_memoria[nodo_idx].lazy_invert = false;
}
// Divide un Treap en dos Treaps: `izq` (elementos con k menores) y `der` (elementos con k mayores)
void dividir(int root, int k, int& izq, int& der) {
if (root == 0) {
izq = 0;
der = 0;
return;
}
push_down(root); // Propagar lazy antes de dividir
int tam_subarbol_izq = treap_memoria[treap_memoria[root].hijo_izq].tamano;
if (k <= tam_subarbol_izq) { // El punto de división está en el subárbol izquierdo
der = root;
dividir(treap_memoria[root].hijo_izq, k, izq, treap_memoria[root].hijo_izq);
} else { // El punto de división está en el subárbol derecho (o el nodo actual)
izq = root;
dividir(treap_memoria[root].hijo_der, k - tam_subarbol_izq - 1, treap_memoria[root].hijo_der, der);
}
push_up(root); // Actualizar tamaño después de la división
}
// Une dos Treaps: `izq` y `der` (todos los elementos de `izq` son menores que los de `der`)
int unir(int izq, int der) {
if (izq == 0 || der == 0) {
return izq ? izq : der;
}
push_down(izq); // Propagar lazy antes de unir
push_down(der); // Propagar lazy antes de unir
if (treap_memoria[izq].prioridad > treap_memoria[der].prioridad) {
treap_memoria[izq].hijo_der = unir(treap_memoria[izq].hijo_der, der);
push_up(izq);
return izq;
} else {
treap_memoria[der].hijo_izq = unir(izq, treap_memoria[der].hijo_izq);
push_up(der);
return der;
}
}
int raiz_treap = 0; // La raíz del Treap global
// Inserta un valor en el Treap en una posición dada (basado en índice)
void insertar_en_posicion(int val, int pos) {
int t1, t2;
dividir(raiz_treap, pos - 1, t1, t2); // Dividir en [1, pos-1] y [pos, N]
raiz_treap = unir(unir(t1, crear_nodo(val)), t2); // Unir t1, el nuevo nodo y t2
}
// Invierte un rango [L, R] en el Treap
void invertir_rango_treap(int l, int r) {
int t1, t2, t3;
dividir(raiz_treap, r, t1, t3); // t1 = [1, R], t3 = [R+1, N]
dividir(t1, l - 1, t1, t2); // t1 = [1, L-1], t2 = [L, R]
treap_memoria[t2].lazy_invert ^= 1; // Marcar el segmento t2 para inversión
raiz_treap = unir(unir(t1, t2), t3); // Unir los tres segmentos
}
// Imprime el Treap en orden (inorder traversal)
void imprimir_treap_inorder(int nodo_idx) {
if (nodo_idx == 0) return;
push_down(nodo_idx); // Propagar lazy antes de imprimir hijos
imprimir_treap_inorder(treap_memoria[nodo_idx].hijo_izq);
printf("%d ", treap_memoria[nodo_idx].valor);
imprimir_treap_inorder(treap_memoria[nodo_idx].hijo_der);
}
int main() {
int n_initial_elements, m_operations;
scanf("%d %d", &n_initial_elements, &m_operations);
// Insertar los elementos iniciales 1, 2, ..., n
for (int i = 1; i <= n_initial_elements; ++i) {
insertar_en_posicion(i, i);
}
// Realizar operaciones de inversión
for (int i = 0; i < m_operations; ++i) {
int range_l, range_r;
scanf("%d %d", &range_l, &range_r);
invertir_rango_treap(range_l, range_r);
}
// Imprimir el estado final del Treap
imprimir_treap_inorder(raiz_treap);
printf("\n");
return 0;
}
DP por Dígitos
La programación dinámica por dígitos (Digit DP) es una técnica utilizada para contar números en un rango \([L, R]\) que satisfacen ciertas propiedades. Se construye la solución dígito por dígito, utilizando memorización para evitar recálculos.
#include <iostream>
#include <vector>
#include <string>
#include <algorithm> // Para std::swap
#include <cstring> // Para memset
#include <cstdio> // Para scanf/printf
long long limite_inferior_rango, limite_superior_rango;
// `memo_dp[pos][count][is_leading_zero][is_tight]`
// Para este problema específico (contar ocurrencias de un dígito X),
// `memo_dp[pos]` es suficiente ya que el resto de estados no son necesarios para el memo.
// Pero la `dfs` necesita esos parámetros.
long long memo_dp[15]; // Solo necesitamos memoizar por posición para este problema (para cada target_digit)
long long potencias_10[15]; // potencias_10[i] = 10^i
std::vector<int> digitos_del_numero; // Almacena los dígitos del número (ej. 123 -> {3,2,1})
// Función DFS para Digit DP
// `idx`: posición del dígito actual (desde el más significativo hacia 0)
// `target_digit`: el dígito específico que estamos buscando
// `es_cero_inicial`: true si los dígitos anteriores fueron todos cero
// `es_limite_superior`: true si estamos restringidos por los dígitos del número original
// `contar_ocurrencias`: Este es el valor que queremos acumular.
long long dp_dfs(int idx, int target_digit, bool es_cero_inicial, bool es_limite_superior) {
// Caso base: si hemos procesado todos los dígitos
if (idx == -1) {
return 0; // No hay más dígitos para procesar, no se añade ninguna ocurrencia aquí
}
// Si no estamos en un estado restringido (no hay ceros iniciales y no estamos en el límite superior)
// y ya hemos calculado este estado, devolver el valor memorizado.
// IMPORTANTE: Para este problema, `memo_dp` debe ser re-inicializado para cada `target_digit`.
// O bien `memo_dp` incluye `target_digit` como dimensión. Aquí, lo reseteamos implícitamente
// ya que `sumar_apariciones` llama a `memset` cada vez.
if (!es_cero_inicial && !es_limite_superior && memo_dp[idx] != -1) {
return memo_dp[idx];
}
long long count_total_apariciones = 0;
int limite_actual_digito = es_limite_superior ? digitos_del_numero[idx] : 9;
for (int digito_actual = 0; digito_actual <= limite_actual_digito; ++digito_actual) {
if (es_cero_inicial && digito_actual == 0) {
// Si es un cero inicial, no cuenta como una ocurrencia de 0 si target_digit es 0.
// Y no cuenta para otros target_digits.
count_total_apariciones += dp_dfs(idx - 1, target_digit, true, es_limite_superior && (digito_actual == limite_actual_digito));
} else {
// Si el dígito actual es el dígito objetivo
if (digito_actual == target_digit) {
// Sumar 1 (por esta ocurrencia) + las ocurrencias en los dígitos restantes
// Y las ocurrencias en los números formados por los dígitos a la derecha (potencias_10[idx])
count_total_apariciones += dp_dfs(idx - 1, target_digit, false, es_limite_superior && (digito_actual == limite_actual_digito));
count_total_apariciones += potencias_10[idx]; // Ocurrencias en posiciones más bajas
} else {
// No es el dígito objetivo, solo sumar las ocurrencias en los dígitos restantes
count_total_apariciones += dp_dfs(idx - 1, target_digit, false, es_limite_superior && (digito_actual == limite_actual_digito));
}
}
}
if (!es_cero_inicial && !es_limite_superior) {
memo_dp[idx] = count_total_apariciones;
}
return count_total_apariciones;
}
// Función para calcular las apariciones de `target_digit` en números hasta `N`
long long sumar_apariciones(long long N, int target_digit) {
digitos_del_numero.clear();
if (N == 0) { // Caso especial: si N es 0, las ocurrencias de 0 son 1, de otros dígitos 0.
return (target_digit == 0 ? 1 : 0);
}
long long temp_N = N;
while (temp_N > 0) {
digitos_del_numero.push_back(temp_N % 10);
temp_N /= 10;
}
memset(memo_dp, -1, sizeof(memo_dp)); // Resetear memo_dp para cada target_digit
// La función original tiene un tratamiento más directo para el `target_digit`
// que es un poco diferente. Si el `target_digit` es 0, el `es_cero_inicial` es importante.
// Para simplificar, podemos adaptar la lógica para contar apariciones de 0 sin ser "leading zero".
// La implementación de abajo es una forma estándar de contar ocurrencias de un dígito.
// La parte `now[l] = now[l-1] + ksm[l-1] * c[l];` del código original parece precalcular
// el número de formas de rellenar los sufijos cuando el prefijo ya "estableció" un `target_digit`.
// Vamos a usar una versión más clásica de Digit DP que cuenta apariciones directamente.
long long ans = 0;
// La estrategia para contar un dígito X en un número N:
// Dividir N en dígitos, iterar desde el más significativo al menos significativo.
//
// Función auxiliar para calcular el número de veces que aparece `d` en el rango [1, N]
// Ejemplo: `count(N, d)`
//
// Adapto el `dfs` para contar ocurrencias.
// `solve(idx, count, leading_zeros, tight, target_digit)`
// La clave es que cada vez que `digito_actual == target_digit`, se suma.
// La `potencias_10[idx]` en el original es para contar las ocurrencias en los números formados por el sufijo
// cuando un prefijo *ya* incluye el dígito objetivo en `idx`.
// La versión aquí lo hará en cada nodo recursivo que *elija* el `target_digit`.
// El snippet original tiene esta complejidad:
// if(f0 && i == 0) cnt += dfs(p-1,x,1,lim && (i==lst)); // Zero inicial, no cuenta aún para 0
// else if(i == x && lim && i == lst) cnt += now[p-1] + 1 + dfs(p-1,x,0,lim && (i==lst)); // Digito X y en limite
// else if(i == x) cnt += ksm[p-1] + dfs(p-1,x,0,lim && (i==lst)); // Digito X
// else cnt += dfs(p-1,x,0,lim && (i==lst)); // Otro digito
// Mi `dp_dfs` cuenta todas las apariciones de `target_digit`.
// Los `now[p-1]` y `ksm[p-1]` del original son precalculados.
// Para `now[p-1]` + 1 (cuando es `lim && i==lst`): esto cuenta las veces que un `target_digit`
// aparece en el resto del número *sin que se haya pasado el límite*, más 1 por el dígito actual.
// Para `ksm[p-1]` (cuando `i==x`): esto cuenta las veces que `target_digit` aparece en los `p-1`
// lugares restantes, cuando el dígito actual no está restringido por el límite.
// Mi `dp_dfs` (simplificado) para contar las ocurrencias de un dígito `target_digit`:
// `dfs(idx, target_digit, is_leading_zero, is_tight)`
// Si `is_leading_zero` y `target_digit` es 0, no contar el 0 principal.
// Si `digito_actual == target_digit` Y no es `is_leading_zero` Y `target_digit` es 0, entonces +1.
// Si `digito_actual == target_digit` Y `target_digit` no es 0, entonces +1.
// La versión clásica de Digit DP para contar ocurrencias es:
// `solve(pos, tight, lead, target)`
// `res = 0`
// `upper = tight ? a[pos] : 9`
// `for d from 0 to upper`:
// ` if lead && d==0`: `res += solve(pos+1, tight && d==upper, true, target)`
// ` else`:
// ` res += solve(pos+1, tight && d==upper, false, target)`
// ` if d==target`: `res += 1` // Suma 1 por la aparición de 'd'
// Esta es para contar los NÚMEROS que tienen el dígito. No la SUMA de las apariciones.
// Para la SUMA de apariciones:
// `solve(pos, tight, lead, target)` regresa `pair<count_of_target_digit count_of_numbers="">`
// `res_count = 0, res_num = 0`
// `for d from 0 to upper`:
// ` new_count, new_num = solve(pos+1, tight && d==upper, lead && d==0, target)`
// ` if d==target && !(lead && d==0)`:
// ` res_count += new_count + new_num` // `new_num` es cuántos números hay a la derecha, cada uno recibe un `d`.
// ` else`: `res_count += new_count`
// ` res_num += new_num`
// Esta es la forma correcta de SUMAR las ocurrencias.
// El snippet original tiene una manera directa pero concisa. Vamos a re-implementar usando esa lógica explícita
// para las ocurrencias en `now[p-1]` y `ksm[p-1]` con mis variables.
std::vector<int> current_digits;
long long temp_num = N;
if (N == 0) current_digits.push_back(0); // Para N=0, un solo dígito 0
while(temp_num > 0) {
current_digits.push_back(temp_num % 10);
temp_num /= 10;
}
std::reverse(current_digits.begin(), current_digits.end()); // Dígitos en orden msb a lsb
memset(memo_dp, -1, sizeof(memo_dp)); // Resetear memo para el nuevo target_digit
// dp_digit_count[i] = número de apariciones de 'target_digit' en números de longitud 'i' (0-indexed)
// Esto se puede precalcular o calcular recursivamente.
// La idea es que la DP tradicional ya lo tiene, solo hay que usarla.
// La lógica de `now[p-1]` es `dfs(idx-1, ...)` (sin restricciones) + `sum_of_numbers(idx-1)` * (10^{idx-1}).
// Vamos a hacer una función diferente que sea más fácil de traducir desde el original
// ya que `dfs` tal como está en el snippet no es el `dp_dfs` generalizado.
// Función de recursión con el estilo del original
std::function<long bool="" int="" long=""> calculate_occurrences =
[&](int p_idx, int x, bool f0, bool lim) -> long long {
if (p_idx == -1) return 0; // No quedan dígitos
if (!f0 && !lim && memo_dp[p_idx] != -1) return memo_dp[p_idx];
long long current_count = 0;
int max_digit_val = lim ? current_digits[p_idx] : 9; // El dígito más significativo es current_digits[p_idx]
for (int digit = 0; digit <= max_digit_val; ++digit) {
if (f0 && digit == 0) { // Es un cero inicial
current_count += calculate_occurrences(p_idx - 1, x, true, lim && (digit == max_digit_val));
} else if (digit == x) { // El dígito actual es el objetivo
// Sumar las ocurrencias de 'x' en el sufijo, y si estamos en el límite superior
// (es decir, el número ya "coincide" con el prefijo de N hasta ahora),
// sumar 1 (por la posición actual) + la cantidad de números que se pueden formar con los dígitos restantes.
if (lim && digit == max_digit_val) {
// Si estamos en el límite superior y el dígito actual es igual al dígito de N en esta posición,
// entonces contamos el dígito actual (1), y luego contamos cuántos números pueden formarse
// con los dígitos de N a la derecha + 1 (para el propio número)
// (similar a `now[p-1] + 1` en el original, `now` es la suma de los sufijos)
long long suffix_num_val = 0; // Valor numérico del sufijo de N hasta la posición p_idx
for(int k=0; k<p_idx; ++k) suffix_num_val = suffix_num_val * 10 + current_digits[k];
current_count += calculate_occurrences(p_idx - 1, x, false, lim && (digit == max_digit_val));
current_count += suffix_num_val + 1; // 1 por el dígito actual, y suffix_num_val por los números que se forman
} else {
// Si el dígito actual es 'x' y no estamos en el límite estricto o no es el dígito límite,
// entonces hay potencias_10[p_idx] números que empiezan con este prefijo
// y este dígito 'x', donde 'x' aparecerá en la posición actual.
current_count += calculate_occurrences(p_idx - 1, x, false, lim && (digit == max_digit_val));
current_count += potencias_10[p_idx]; // Todas las veces que 'x' aparece en esta posición para los números menores
}
} else { // El dígito actual no es el objetivo
current_count += calculate_occurrences(p_idx - 1, x, false, lim && (digit == max_digit_val));
}
}
if (!f0 && !lim) memo_dp[p_idx] = current_count;
return current_count;
};
// Ajuste al estilo del original, con índice p (desde N-1 hasta 0)
// El original usaba 1-based indexing para 'p' donde 'p' era la longitud de la parte restante.
// Aquí, `p_idx` es el índice del dígito actual en `current_digits`
// (si `current_digits` es `[d_k, d_{k-1}, ..., d_0]`, entonces `p_idx` va de `k` a `0`).
// `current_digits` está en orden LSB a MSB si se usa `push_back(N%10)`.
// Si `reverse` se usa, es MSB a LSB.
// El original lo usa LSB a MSB porque `p` baja y `c[p]` es el `p`-ésimo dígito.
// Vamos a mantener `digitos_del_numero` como LSB a MSB para `dfs` desde `len-1` a `0`.
digitos_del_numero.clear();
long long temp_val = N;
if (temp_val == 0) digitos_del_numero.push_back(0); // manejar N=0
while (temp_val > 0) {
digitos_del_numero.push_back(temp_val % 10);
temp_val /= 10;
}
memset(memo_dp, -1, sizeof(memo_dp)); // Resetear memo para este target_digit
// `dfs(len-1, target_digit, true, true)`
// p_idx: índice del dígito actual (de derecha a izquierda, 0 es el dígito de las unidades)
// x: el dígito objetivo
// f0: true si todos los dígitos hasta ahora han sido 0 (para manejar ceros iniciales)
// lim: true si estamos restringidos por el número original
// Función de recursión adaptada al estilo de conteo de Digit DP para apariciones
// Esta es una implementación más estándar que el snippet, que tenía optimizaciones
// de `now` y `ksm` que son difíciles de replicar genéricamente sin más contexto.
std::function<long bool="" int="" long=""> count_digit_occurrences =
[&](int pos, int d_target, bool is_leading_zero, bool is_tight) -> long long {
if (pos == -1) return 0;
if (!is_leading_zero && !is_tight && memo_dp[pos] != -1) return memo_dp[pos];
long long current_total = 0;
int upper_bound = is_tight ? digitos_del_numero[pos] : 9;
for (int digit = 0; digit <= upper_bound; ++digit) {
if (is_leading_zero && digit == 0) {
current_total += count_digit_occurrences(pos - 1, d_target, true, is_tight && (digit == upper_bound));
} else {
current_total += count_digit_occurrences(pos - 1, d_target, false, is_tight && (digit == upper_bound));
if (digit == d_target) {
current_total += potencias_10[pos]; // Se suma la cantidad de números que se pueden formar con los pos dígitos restantes.
}
}
}
if (!is_leading_zero && !is_tight) memo_dp[pos] = current_total;
return current_total;
};
return count_digit_occurrences(digitos_del_numero.size() - 1, target_digit, true, true);
}
int main() {
potencias_10[0] = 1;
for (int i = 1; i <= 14; ++i) { // Potencias hasta 10^14 (para 15 dígitos)
potencias_10[i] = potencias_10[i - 1] * 10LL;
}
scanf("%lld %lld", &limite_inferior_rango, &limite_superior_rango);
if (limite_inferior_rango > limite_superior_rango) {
std::swap(limite_inferior_rango, limite_superior_rango);
}
// Calcular las ocurrencias de cada dígito de 0 a 9 en el rango [L, R]
for (int d = 0; d <= 9; ++d) {
// La cuenta en [L, R] es (cuenta en [0, R]) - (cuenta en [0, L-1])
printf("%lld ", sumar_apariciones(limite_superior_rango, d) - sumar_apariciones(limite_inferior_rango - 1, d));
}
printf("\n");
return 0;
}
</long></long></int></count_of_target_digit>