Optimización de Entrada/Salida (Fast I/O)

Propósito

Resolver los cuellos de botella en operaciones de entrada y salida cuando se procesan volúmenes masivos de datos (del orden de $10^6$). El uso de flujos estándar sin optimizar puede provocar erores de Tiempo Límite Excedido (TLE).

Complejidad

• Procesamiento por carácter: $O(1)$
• Eficiencia general: Multiplica la velocidad por 5 o 10 en comparación con cin/cout por defecto, igualando o superando a scanf/printf.

Implemnetación

#include <iostream>
#include <string>

// Configuración básica para desincronizar flujos estándar
void setupFastIO() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
}

// Lectura acelerada para enteros de 32 bits
inline int32_t readInt() {
    int32_t result = 0;
    int8_t sign = 1;
    char c = getchar();
    
    while (c < '0' || c > '9') {
        if (c == '-') sign = -1;
        c = getchar();
    }
    
    while (c >= '0' && c <= '9') {
        result = (result << 3) + (result << 1) + (c - '0');
        c = getchar();
    }
    
    return result * sign;
}

// Lectura acelerada para enteros de 64 bits
inline int64_t readLong() {
    int64_t result = 0;
    int8_t sign = 1;
    char c = getchar();
    
    while (c < '0' || c > '9') {
        if (c == '-') sign = -1;
        c = getchar();
    }
    
    while (c >= '0' && c <= '9') {
        result = (result << 3) + (result << 1) + (c - '0');
        c = getchar();
    }
    
    return result * sign;
}

// Lectura de palabras (detiene en espacios o saltos de línea)
inline std::string readWord() {
    std::string word;
    char c = getchar();
    while (c == ' ' || c == '\n' || c == '\t' || c == '\r') {
        c = getchar();
    }
    while (c != ' ' && c != '\n' && c != '\t' && c != '\r' && c != EOF) {
        word += c;
        c = getchar();
    }
    return word;
}

// Lectura de línea completa
inline std::string readLine() {
    std::string line;
    char c = getchar();
    while (c != '\n' && c != EOF) {
        line += c;
        c = getchar();
    }
    return line;
}

Casos de Uso

• Cuando el volumen de entrada supera los $10^5$ elementos.
• Problemas con límites de tiempo extremadamente restrictivos.
• Lectura de cadenas de texto masivas donde std::getline resulta ineficiente.

Estructura de Datos Disjuntos (DSU / Union-Find)

Propósito

Gestionar de manera eficiente la fusión de conjuntos y la verificación de pertenencia a un mismo grupo. Es la estructura fundamental para resolver problemas de conectividad en grafos.

Complejidad

• Operaciones find y union: $O(\alpha(n))$ por operación, donde $\alpha$ es la función inversa de Ackermann, lo que en la práctica se considera $O(1)$.

Implementación

#include <vector>
#include <numeric>

class UnionFind {
private:
    std::vector<int> representative;
    std::vector<int> depth;

public:
    explicit UnionFind(int elements) {
        representative.resize(elements + 1);
        depth.assign(elements + 1, 0);
        std::iota(representative.begin(), representative.end(), 0);
    }

    int findSet(int node) {
        if (representative[node] != node) {
            representative[node] = findSet(representative[node]);
        }
        return representative[node];
    }

    bool unionSets(int nodeA, int nodeB) {
        int rootA = findSet(nodeA);
        int rootB = findSet(nodeB);
        
        if (rootA == rootB) return false;

        if (depth[rootA] < depth[rootB]) {
            representative[rootA] = rootB;
        } else if (depth[rootA] > depth[rootB]) {
            representative[rootB] = rootA;
        } else {
            representative[rootB] = rootA;
            depth[rootA]++;
        }
        return true;
    }

    bool isConnected(int nodeA, int nodeB) {
        return findSet(nodeA) == findSet(nodeB);
    }
};

Casos de Uso

• Determinar si dos nodos en un grafo están en la misma componente conexa.
• Implementación del algoritmo de Kruskal para árboles de expansión mínima.
• Problemas de agrupamiento o detección de ciclos en grafos no dirigidos.

Árbol de Fenwick (Binary Indexed Tree)

Propósito

Permite realizar actualizaciones en puntos específicos y consultas de sumas de prefijos o intervalos de manera altamente eficiente, con una implementación compacta y constantes de tiempo muy pequeñas.

Complejidad

• Actualización puntual: $O(\log n)$
• Consulta de intervalo/prefijo: $O(\log n)$

Implementación

#include <vector>

class FenwickTree {
private:
    std::vector<int64_t> bitArray;
    int maxIndex;

    int getLowestBit(int idx) {
        return idx & (-idx);
    }

public:
    explicit FenwickTree(int size) {
        maxIndex = size;
        bitArray.assign(size + 1, 0);
    }

    void addValue(int idx, int64_t delta) {
        for (; idx <= maxIndex; idx += getLowestBit(idx)) {
            bitArray[idx] += delta;
        }
    }

    int64_t getPrefixSum(int idx) {
        int64_t sum = 0;
        for (; idx > 0; idx -= getLowestBit(idx)) {
            sum += bitArray[idx];
        }
        return sum;
    }

    int64_t getRangeSum(int left, int right) {
        return getPrefixSum(right) - getPrefixSum(left - 1);
    }
};

Casos de Uso

• Cálculo dinámico de sumas en subarreglos con actualizaciones frecuentes.
• Resolución del problema de inversiones en un arreglo (contar pares invertidos).
• Consultas de frecuencia acumulada en problemas de conteo.

Hashing Polinómico de Cadenas

Propósito

Transformar subcadenas en valores numéricos (hashes) para permitir la comparación de igualdad entre dos subcadenas en tiempo constante, sirviendo como una alternativa eficiente a algoritmos como KMP en ciertos escenarios.

Complejidad

• Preprocesamiento de la cadena: $O(n)$
• Consulta de hash de subcadena: $O(1)$

Implementación

#include <string>
#include <vector>

class PolynomialHash {
private:
    using HashType = uint64_t;
    static constexpr HashType BASE = 131;
    static constexpr HashType MOD = 1000000007; 
    
    std::vector<HashType> prefixHash;
    std::vector<HashType> powers;

public:
    explicit PolynomialHash(const std::string& text) {
        int len = text.length();
        prefixHash.resize(len + 1, 0);
        powers.resize(len + 1, 1);

        for (int i = 1; i <= len; ++i) {
            powers[i] = (powers[i - 1] * BASE) % MOD;
            prefixHash[i] = (prefixHash[i - 1] * BASE + text[i - 1]) % MOD;
        }
    }

    HashType getSubstringHash(int left, int right) {
        HashType hashVal = (prefixHash[right] - (prefixHash[left - 1] * powers[right - left + 1]) % MOD + MOD) % MOD;
        return hashVal;
    }
};

Casos de Uso

• Verificación rápida de si dos subcadenas dentro de un texto son idénticas.
• Búsqueda de patrones dentro de cadenas de texto largas.
• Detección de subcadenas repetidas o palíndromos (combinando hashes directos e inversos).