Friki Work

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 ...