En este artículo, se presentan soluciones a problemas típicos de competiciones de programación, enfocándonos en el uso de operaciones XOR, componentes fuertemente conexos (SCC) y técnicas de árbol.

Problema 1: Consultas de XOR con Operaciones Dinámicas

Este problema requiere manejar consultas dinámicas donde se puede debilitar a consultas de suma XOR. Las operaciones se diseñan para mantener la suma XOR de un conjunto, permitiendo enserciones y combinaciones basadas en XOR. La solución evita construcciones explícitas y utiliza una estructura de array simple para rastrear resultados.

#include <bits>
using namespace std;
const int MAX_TAM = 1e6 + 10;
int respuestaAnterior = 0, totalConsultas;
int datos[MAX_TAM];
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cin >> totalConsultas;
    int indice = 0;
    for (int iter = 1; iter <= totalConsultas; ++iter) {
        int tipo;
        cin >> tipo;
        tipo ^= respuestaAnterior;
        if (tipo == 1) {
            int valor, multiplicador;
            cin >> valor >> multiplicador;
            valor ^= respuestaAnterior;
            multiplicador ^= respuestaAnterior;
            datos[++indice] = (multiplicador & 1) * valor;
        } else if (tipo == 2) {
            int pos1, pos2;
            cin >> pos1 >> pos2;
            pos1 ^= respuestaAnterior;
            pos2 ^= respuestaAnterior;
            datos[++indice] = datos[pos1] ^ datos[pos2];
        } else if (tipo == 3) {
            int pos, valor, multiplicador;
            cin >> pos >> valor >> multiplicador;
            pos ^= respuestaAnterior;
            valor ^= respuestaAnterior;
            multiplicador ^= respuestaAnterior;
            datos[++indice] = datos[pos] ^ ((multiplicador & 1) * valor);
        } else if (tipo == 4) {
            int pos;
            cin >> pos;
            pos ^= respuestaAnterior;
            int res = datos[pos];
            cout << res << "\n";
            respuestaAnterior = res;
        }
    }
    return 0;
}
</bits>

Problema 2: Compresión de Colores en Grafos con Restricciones Temporales

Este problema implica construir un grafo dirigido con colores que tienen orden temporal, donde en cada paso se elimina un SCC completo. Se presenta un enfoque que evita construir el grafo explícitamente, usando Kosaraju con optimización de segment trees y descomposición en árboles para manejar LCA y recorridos eficientes. La complejidad se reduce a O(n log n) mediante compersión de caminos y manejo de DFS order.

#include <bits>
using namespace std;
const int MAX_NODOS = 5e5 + 10;
int numNodos, colores[MAX_NODOS], contador, ultimaPos[MAX_NODOS], padre[MAX_NODOS];
int cabeza[MAX_NODOS], maximo[MAX_NODOS], resultado[MAX_NODOS], total, pila[MAX_NODOS];
int hijoPesado[MAX_NODOS], profundidad[MAX_NODOS], listaAdy[MAX_NODOS], segTree[MAX_NODOS << 2];
int indicePos[MAX_NODOS], suma;
long long respuestaTotal;

int leerEntrada() {
    int x = 0;
    char ch = getchar();
    while (ch < '0' || ch > '9') ch = getchar();
    while (ch >= '0' && ch <= '9') {
        x = x * 10 + (ch - '0');
        ch = getchar();
    }
    return x;
}

struct Arista {
    int destino, siguiente;
} aristas[MAX_NODOS << 1];

void agregarArista(int u, int v) {
    aristas[++contador] = {v, listaAdy[u]};
    listaAdy[u] = contador;
    aristas[++contador] = {u, listaAdy[v]};
    listaAdy[v] = contador;
}

void construirSegTree(int ini, int fin, int nodo) {
    if (ini == fin) {
        segTree[nodo] = listaAdy[colores[resultado[ini]]];
        return;
    }
    int medio = (ini + fin) >> 1;
    construirSegTree(ini, medio, nodo << 1);
    construirSegTree(medio + 1, fin, nodo << 1 | 1);
    segTree[nodo] = min(segTree[nodo << 1], segTree[nodo << 1 | 1]);
}

void actualizarSegTree(int ini, int fin, int pos, int nodo) {
    if (ini == fin) {
        segTree[nodo] = numNodos + 1;
        return;
    }
    int medio = (ini + fin) >> 1;
    if (pos <= medio) actualizarSegTree(ini, medio, pos, nodo << 1);
    else actualizarSegTree(medio + 1, fin, pos, nodo << 1 | 1);
    segTree[nodo] = min(segTree[nodo << 1], segTree[nodo << 1 | 1]);
}

void consultaSegTree(int ini, int fin, int izq, int der, int limite, int nodo);

void procesarColor(int color) {
    cabeza[color] = 0;
    ++suma;
    int nodoActual = ultimaPos[color];
    do {
        actualizarSegTree(1, numNodos, indicePos[nodoActual], 1);
        ++total;
    } while ((nodoActual = hijoPesado[nodoActual]) > 0);
    nodoActual = ultimaPos[color];
    do {
        consultaSegTree(1, numNodos, indicePos[nodoActual] + 1, maximo[nodoActual], profundidad[nodoActual], 1);
    } while ((nodoActual = hijoPesado[nodoActual]) > 0);
}

void consultaSegTree(int ini, int fin, int izq, int der, int limite, int nodo) {
    if (segTree[nodo] > limite || izq > der) return;
    if (ini == fin) {
        procesarColor(colores[resultado[ini]]);
        return;
    }
    int medio = (ini + fin) >> 1;
    if (izq <= medio) consultaSegTree(ini, medio, izq, der, limite, nodo << 1);
    if (der > medio) consultaSegTree(medio + 1, fin, izq, der, limite, nodo << 1 | 1);
}

void DFS(int nodo, int padreNodo) {
    padre[nodo] = padreNodo;
    profundidad[nodo] = profundidad[padreNodo] + 1;
    cabeza[nodo] = 1;
    resultado[++contador] = nodo;
    indicePos[nodo] = maximo[nodo] = contador;
    for (int i = listaAdy[nodo]; i; i = aristas[i].siguiente) {
        int vecino = aristas[i].destino;
        if (vecino != padreNodo) {
            DFS(vecino, nodo);
            cabeza[nodo] += cabeza[vecino];
            maximo[nodo] = maximo[vecino];
            if (cabeza[hijoPesado[nodo]] < cabeza[vecino]) hijoPesado[nodo] = vecino;
        }
    }
}

void descomponerArbol(int nodo) {
    if (hijoPesado[nodo]) {
        cabeza[hijoPesado[nodo]] = cabeza[nodo];
        descomponerArbol(hijoPesado[nodo]);
    }
    for (int i = listaAdy[nodo]; i; i = aristas[i].siguiente) {
        int vecino = aristas[i].destino;
        if (vecino != padre[nodo] && vecino != hijoPesado[nodo]) {
            cabeza[vecino] = vecino;
            descomponerArbol(vecino);
        }
    }
}

int calcularLCA(int u, int v) {
    while (cabeza[u] != cabeza[v]) {
        if (profundidad[cabeza[u]] < profundidad[cabeza[v]]) v = padre[cabeza[v]];
        else u = padre[cabeza[u]];
    }
    return (profundidad[u] < profundidad[v]) ? u : v;
}

int encontrar(int nodo) {
    return nodo ? (cabeza[colores[padre[nodo]]] ? padre[nodo] = encontrar(padre[nodo]) : padre[nodo]) : 0;
}

void resolver(int color) {
    cabeza[color] = 1;
    int nodoActual = ultimaPos[color];
    do {
        int ancestro = encontrar(nodoActual);
        while (profundidad[ancestro] >= listaAdy[color]) {
            resolver(colores[ancestro]);
            ancestro = encontrar(ancestro);
        }
    } while ((nodoActual = hijoPesado[nodoActual]) > 0);
    pila[++contador] = color;
}

int main() {
    numNodos = leerEntrada();
    for (int i = 1; i <= numNodos; ++i) colores[i] = leerEntrada();
    for (int i = 1, u, v; i < numNodos; ++i) {
        u = leerEntrada();
        v = leerEntrada();
        agregarArista(u, v);
    }
    contador = 0;
    DFS(1, 0);
    contador = 0;
    for (int i = 1; i <= numNodos; ++i) cabeza[i] = 0;
    cabeza[1] = 1;
    descomponerArbol(1);
    for (int i = 1; i <= numNodos; ++i) listaAdy[i] = 0;
    for (int i = 1; i <= numNodos; ++i) {
        if (listaAdy[colores[i]]) {
            listaAdy[colores[i]] = calcularLCA(listaAdy[colores[i]], i);
            hijoPesado[i] = ultimaPos[colores[i]];
            ultimaPos[colores[i]] = i;
        } else {
            listaAdy[colores[i]] = ultimaPos[colores[i]] = i;
            hijoPesado[i] = 0;
        }
    }
    for (int i = 1; i <= numNodos; ++i) listaAdy[i] = profundidad[listaAdy[i]];
    construirSegTree(1, numNodos, 1);
    for (int i = 1; i <= numNodos; ++i) cabeza[i] = pila[i] = 0;
    for (int i = 1; i <= numNodos; ++i) {
        if (ultimaPos[i] && !cabeza[i]) {
            resolver(i);
        }
    }
    for (int i = contador; i; --i) {
        if (cabeza[pila[i]]) {
            suma = 0;
            total = 0;
            procesarColor(pila[i]);
            respuestaTotal += 1LL * suma * total;
        }
    }
    cout << respuestaTotal;
    return 0;
}
</bits>

Problema 3: Programación Dinámica con Inclusión-Exclusión

Este problema se aborda mediante una técnica de contaje basada en inclusión-exclusión, típica en programación dinámica para optimizar conteos con restricciones complejas.