Introduccion a los Monticulos Mergeables

Los monticulos mergeables, basados en la estructura de arbol izquierdista, son una solucion avanzada para gestionar colas de prioridad con capacidad de fusion rapida. A diferencia de las implementaciones estandar, estos permiten combinar dos monticulos en tiempo logaritmico, manteniendo propiedades estructurales clave.

Operaciones Soportadas

• Operaciones basicas de un monticulo: insercion, extraccion del minimo o maximo.
• Fusion (merge): integra dos monticulos en uno solo, preservando la propiedad izquierdista para mantener eficiencia.
• Mejora en velocidad de union, ideal para algoritmos que requieren multiples combinaciones dinamicas.

Uso de la Biblioteca pbds en C++

La biblioteca ext/pb_ds/priority_queue.hpp proporciona una implementacion optimizada. Se declara con el espacio de nombres __gnu_pbds, y se pueden fusionar dos instancias mediante el metodo join, que utiliza internamente un monticulo de pares por defecto.

Ejemplo Practico: Plantilla de Monticulo Mergeable

Descripcion del Problema

Inicialmente existen n monticulos minimos, cada uno conteniendo un unico valor. Se deben procesar dos tipos de operaciones:

1. Fusionar los monticulos que contienen los valores en las posiciones x e y, ignorando la operacion si alguno ya fue eliminado o estan en el mismo monticulo.
2. Extraer e imprimir el valor minimo del monticulo que contiene al valor en la posicion x, eliminandolo; si x ya fue eliminado, se imprime -1.

Formato de Entrada

La primera linea contiene dos enteros n y m, representando el numero inicial de monticulos y la cantidad de operaciones. La segunda linea tiene n enteros, los valores iniciales. Las siguientes m lineas describen las operaciones.

Formato de Salida

Por cada opeeracion de tipo 2, se imprime una linea con el resultado.

Ejemplo de Entrada

5 5
1 5 4 2 3
1 1 5
1 2 5
2 2
1 4 2
2 2

Ejemplo de Salida

1
2

Notas sobre los Datos

Para el 30% de los casos, n y m son hasta 10. Para el 70%, hasta 10^3. Para el 100%, alcanzan 10^5, con valores iniciales en rango de enteros.

Solucion

Se implementa una estructura que combina union-find para rastrear componentes con monticulos mergeables de la biblioteca pbds. Cada elemento se almacena con su valor y un identificador unico para manejar prioridades en caso de empates.

Codigo en C++

#include <iostream>
#include <ext/pb_ds/priority_queue.hpp>

using namespace std;
using namespace __gnu_pbds;

const int MAX_ENTRADA = 100005;
int datos[MAX_ENTRADA];
int ancestro[MAX_ENTRADA];
bool fuera[MAX_ENTRADA];

int localizarRaiz(int vertice) {
    while (ancestro[vertice] != vertice) {
        ancestro[vertice] = ancestro[ancestro[vertice]];
        vertice = ancestro[vertice];
    }
    return vertice;
}

struct Registro {
    int clave;
    int pos;
    bool operator<(const Registro& otro) const {
        if (clave == otro.clave) return pos > otro.pos;
        return clave > otro.clave;
    }
};

priority_queue<Registro> colecciones[MAX_ENTRADA];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int total, ops;
    cin >> total >> ops;
    for (int i = 1; i <= total; ++i) {
        cin >> datos[i];
        ancestro[i] = i;
        colecciones[i].push({datos[i], i});
    }
    
    for (int i = 0; i < ops; ++i) {
        int modo;
        cin >> modo;
        if (modo == 1) {
            int a, b;
            cin >> a >> b;
            int raizA = localizarRaiz(a);
            int raizB = localizarRaiz(b);
            if (raizA == raizB || fuera[a] || fuera[b]) continue;
            colecciones[raizA].join(colecciones[raizB]);
            ancestro[raizB] = raizA;
        } else {
            int c;
            cin >> c;
            if (fuera[c]) {
                cout << -1 << '\n';
                continue;
            }
            int raiz = localizarRaiz(c);
            Registro minVal = colecciones[raiz].top();
            colecciones[raiz].pop();
            fuera[minVal.pos] = true;
            cout << minVal.clave << '\n';
        }
    }
    return 0;
}