Friki Work

Últimammente he estado estudiando árboles de segmentos, y como estamos cerca del final del smeestre, mi estudio ha sido intermitente, lo que ha hecho que algunos conceptos no estén completamente claros. Sin embargo, entiendo que no puedo obsesionarme con los detalles, así que he combinado mi estudio con la resolución de problemas para profundiz ...

Estrategia O(N³) Primero se filtran posiciones con valores no nulos que no pueden ser máximos locales. El cálculo utiliza programación dinámica: const int MAX_N = 4e5 + 5; int n_values, sequence[MAX_N], cost[MAX_N]; bool is_visible[MAX_N]; ll dp_table[2005][2005]; int main() { cin >> n_values; for (int pos = 1; pos <= n_values; ...

Aquí se presentan soluciones a varios problemas de la edición Open 2021 del concurso USACO, con explicaciones breves y código reescrito para mejorar la legibilidad y variar la implementación original. Problema G1 – USACO 2021 Open Gold Enfoque: Para cada posición i se almacena anterior[i], el índice del elemento igual más cercano hacia la izqui ...

Introducción al árbol de segmentos #include <cstdio> #include <algorithm> using namespace std; typedef long long ll; const int MAXN = 100010; int n, q; ll arr[MAXN]; ll segtree[MAXN << 2]; ll lazy[MAXN << 2]; void pushUp(int nodo) { segtree[nodo] = segtree[nodo << 1] + segtree[(nodo << 1) | 1]; } voi ...

Primeramente, este parámetro (2L) resulta incómodo, por lo que definiremos L en su lugar. Analicemos el problema en profundidad. Si h_i \le h_{i-1}, para satisfacer las condiciones del problema, debe cumplirse al menos una de las siguientes: L - h_i > h_{i-1} h_i > L - h_{i-1} En esencia, esto significa que o bien L < h_i + h_{i-1} o ...

Problema Se proporcionan \(n\) intervalos. Se puede seleccionar arbitrariamente cualquier subconjunto de estos intervalos (incluyendo el conjunto vacío). Luego, se deben realizar las siguientes operaciones: Para los intervalos seleccionados, se realiza una operación de adición global, es decir, si se selecciona \([l_i, r_i]\, entonces todos lo ...

Este artículo explora tres estructuras de datos fundamentales para resolver problemas eficientes de consulta y actualización en secuencias: el Árbol de Fenwick (o BIT), el Árbol de Segmentos y la Tabla de Dispersión (Sparse Table). Cada una ofrece ventajas particulares dependiendo del tipo de operación requerida. Árbol de Fenwick (Binary Indexe ...