Para manejar operaciones de inversión en subsecuencias de una secuencia inicial a={1,2,...,n} con m operaciones, donde cada operación envierte el intervalo [L,R] y se debe imprimir la secuencia final, se requiere una estructura de datos eficiente. Los árboles de segmentos no pueden realizar inversiones en O(log n), por lo que se recurre a árboles balanceados como el Splay, que permite operaciones de rango mediante rotacioens y etiquetas perezosas.

Concepto del Árbol Splay

El Splay es un árbol de búsqueda binaria autoajustable que, tras cada acceso o modificación, traslada el nodo consultado a la raíz mediante operaciones de rotación. Esto garantiza un costo amortizado de O(log n) por operación. Cada subárbol representa un intervalo contiguo de la secuencia, lo que facilita las operaciones de rango.

Rotación (Rotate)

La rotación es una operación fundamental que reestructura el árbol manteniendo el orden de búsqueda. En el Splay, se modifica no solo los hijos de los nodos involucrados, sino también sus referencias al padre, permitiendo unificar las rotaciones izquierda y derecha en una sola función basada en la posición del nodo respecto a su padre.

void rotar(int u) {
    int x = arbol[u].padre;
    int y = arbol[x].padre;
    int k = u == arbol[x].hijos[1];
    arbol[y].hijos[x == arbol[y].hijos[1]] = u, arbol[u].padre = y;
    arbol[x].hijos[k] = arbol[u].hijos[k ^ 1], arbol[arbol[u].hijos[k ^ 1]].padre = x;
    arbol[u].hijos[k ^ 1] = x, arbol[x].padre = u;
    actualizar(x), actualizar(u);
}

Operación Splay (伸展)

La operación Splay traslada un nodo u a ser hijo de otro nodo k (o a la raíz si k=0) mediante rotaciones dobles. Se distinguen dos casos según la posición relativa de u y su padre x con respecto al abuelo y: si u y x están al mismo lado respecto a y, se rota primero x y luego u; si están en lados opuestos, se rota u dos veces consecutivas. Este método es esencial para mantener la complejidad amortizada.

void splay(int u, int k) {
    while (arbol[u].padre != k) {
        int x = arbol[u].padre;
        int y = arbol[x].padre;
        if (y != k) {
            if ((arbol[x].hijos[1] == u) ^ (arbol[y].hijos[1] == x)) rotar(u);
            else rotar(x);
        }
        rotar(u);
    }
    if (!k) raiz = u;
}

Implementación para Inversión de Secuencias

Para invertir un intervalo [L,R], se accede a los nodos correspondientes a los índices L-1 y R+1 en el Splay, trasladándolos para que el subárbol que representa [L,R] quede como hijo izquierdo del nodo R+1. Se utiliza una etiqueta perezosa (bandera) para marcar subárboles que necesitan inversión, propagándose al acceder a los nodos. Se insertan nodos fictciios en los límites 0 y n+1 para evitar problemas de acceso.

Código Completo

A continuación, se presenta una implementación en C++ con nombres de variables y funciones adaptados al español, manteniendo la lógica original pero con estructura modificada.

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 100005;

struct Nodo {
    int hijos[2], padre, valor;
    int tamano, bandera;
    void inicializar(int p, int v) {
        padre = p, valor = v;
        tamano = 1, bandera = 0;
    }
} arbol[N];
int n, m;
int raiz, contador;

void actualizar(int u) {
    arbol[u].tamano = arbol[arbol[u].hijos[0]].tamano + arbol[arbol[u].hijos[1]].tamano + 1;
}

void propagar(int u) {
    if (arbol[u].bandera) {
        swap(arbol[u].hijos[0], arbol[u].hijos[1]);
        arbol[arbol[u].hijos[0]].bandera ^= 1;
        arbol[arbol[u].hijos[1]].bandera ^= 1;
        arbol[u].bandera = 0;
    }
}

void salida(int u) {
    propagar(u);
    if (arbol[u].hijos[0]) salida(arbol[u].hijos[0]);
    if (1 <= arbol[u].valor && arbol[u].valor <= n) cout << arbol[u].valor << ' ';
    if (arbol[u].hijos[1]) salida(arbol[u].hijos[1]);
}

void rotar(int u) {
    int x = arbol[u].padre;
    int y = arbol[x].padre;
    int k = u == arbol[x].hijos[1];
    arbol[y].hijos[x == arbol[y].hijos[1]] = u, arbol[u].padre = y;
    arbol[x].hijos[k] = arbol[u].hijos[k ^ 1], arbol[arbol[u].hijos[k ^ 1]].padre = x;
    arbol[u].hijos[k ^ 1] = x, arbol[x].padre = u;
    actualizar(x), actualizar(u);
}

void splay(int u, int k) {
    while (arbol[u].padre != k) {
        int x = arbol[u].padre;
        int y = arbol[x].padre;
        if (y != k) {
            if ((arbol[x].hijos[1] == u) ^ (arbol[y].hijos[1] == x)) rotar(u);
            else rotar(x);
        }
        rotar(u);
    }
    if (!k) raiz = u;
}

void insertar(int clave) {
    int u = raiz, p = 0;
    while (u) {
        p = u;
        u = arbol[u].hijos[clave > arbol[u].valor];
    }
    u = ++ contador;
    if (p) arbol[p].hijos[clave > arbol[p].valor] = u;
    arbol[u].inicializar(p, clave);
    splay(u, 0);
}

int obtener_clave(int u, int rango) {
    while (true) {
        propagar(u);
        if (arbol[arbol[u].hijos[0]].tamano >= rango) u = arbol[u].hijos[0];
        else if (arbol[arbol[u].hijos[0]].tamano + 1 == rango) return u;
        else rango -= arbol[arbol[u].hijos[0]].tamano + 1, u = arbol[u].hijos[1];
    }
    return -1;
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 0; i <= n + 1; i ++ ) insertar(i);
    while (m -- ) {
        int l, r;
        scanf("%d%d", &l, &r);
        l = obtener_clave(raiz, l), r = obtener_clave(raiz, r + 2);
        splay(l, 0), splay(r, l);
        arbol[arbol[r].hijos[0]].bandera ^= 1;
    }
    salida(raiz);
    return 0;
}

Errores Comunes en la Implementación

• En la operación splay, cuando k=0, es imprescindible asignar la raíz al nodo u.
• Al buscar el nodo con un rango específico, si el nodo objetivo está en el subárbol derecho, se debe ajustar el rango antes de mover el puntero u.