Descripción del Problema

Se nos presenta una cuadrícula de dimensiones $2 \times C$. El sistema debe soportar tres operaciones fundamentales de manera dinámica sobre este grafo:

1. Establecer una arista antre dos celdas adyacentes.
2. Eliminar una arista existente entre dos celdas adyacentes.
3. Consultar si existe un camino válido (conectividad) entre dos celdas dadas.

Enfoque 1: Descomposición en Bloques y Búsqueda en Anchura

Una alternativa inicial para abordar este problema implica dividir la cuadrícula en bloques de tamaño $\sqrt{C}$. Dentro de cada bloque, utilizamos una estructura de datos de Conjuntos Disjuntos (Union-Find) para rastrear la conectividad local. Las conexiones entre bloques adyacentes se gestionan mediante arreglos de indicadores que actúan como puentes.

Cuando se elimina una arista interna de un bloque, reconstruimos el Union-Find de ese bloque de manera exhaustiva. Para las consultas de conectividad, ejecutamos una Búsqueda en Anchura (BFS) comenzando desde las cuatro esquinas del bloque de origen. El algoritmo explora los puentes hacia bloques adyacentes y verifica si las esquinas alcanzaads pueden conectar con el destino.

Complejidad temporal: $O(C\sqrt{C})$.

#include <iostream>
#include <vector>
#include <queue>
#include <cmath>
#include <algorithm>

using namespace std;

constexpr int MAX_COLS = 1000005;
constexpr int MAX_BLOCKS = 1005;

int totalCols, blockSize, numBlocks;
int blockStart[MAX_BLOCKS], blockEnd[MAX_BLOCKS];
int parent[MAX_COLS * 2];
int colToBlock[MAX_COLS];

int corners[MAX_BLOCKS][4];
bool bridgeRight[MAX_COLS * 2];
bool bridgeLeft[MAX_COLS * 2];

vector<pair<int, int>> blockEdges[MAX_BLOCKS];
vector<pair<int, int>> tempEdges;

struct BFSState {
    int cellId;
    int blockIdx;
};

int findSet(int x) {
    return parent[x] == x ? x : parent[x] = findSet(parent[x]);
}

void unionSet(int x, int y) {
    int rootX = findSet(x), rootY = findSet(y);
    if (rootX != rootY) parent[rootX] = rootY;
}

bool connected(int x, int y) {
    return findSet(x) == findSet(y);
}

inline int getCellId(int row, int col) {
    return (col - 1) * 2 + (row - 1);
}

void rebuildBlock(int bIdx, int excludeU = -1, int excludeV = -1) {
    corners[bIdx][0] = getCellId(1, blockStart[bIdx]);
    corners[bIdx][1] = getCellId(1, blockEnd[bIdx]);
    corners[bIdx][2] = getCellId(2, blockStart[bIdx]);
    corners[bIdx][3] = getCellId(2, blockEnd[bIdx]);

    for (int c = blockStart[bIdx]; c <= blockEnd[bIdx]; ++c) {
        parent[getCellId(1, c)] = getCellId(1, c);
        parent[getCellId(2, c)] = getCellId(2, c);
    }

    tempEdges.clear();
    for (auto& edge : blockEdges[bIdx]) {
        if (edge.first == excludeU && edge.second == excludeV) continue;
        unionSet(edge.first, edge.second);
        tempEdges.push_back(edge);
    }
    blockEdges[bIdx].swap(tempEdges);
}

void initialize() {
    blockSize = max(1, (int)sqrt(totalCols));
    numBlocks = 0;
    for (int c = 1; c <= totalCols; ++c) {
        colToBlock[c] = (c - 1) / blockSize + 1;
        numBlocks = max(numBlocks, colToBlock[c]);
        if (blockStart[colToBlock[c]] == 0) blockStart[colToBlock[c]] = c;
        blockEnd[colToBlock[c]] = max(blockEnd[colToBlock[c]], c);
    }
    for (int b = 1; b <= numBlocks; ++b) rebuildBlock(b);
}

void addEdge(int r1, int c1, int r2, int c2) {
    int u = getCellId(r1, c1), v = getCellId(r2, c2);
    if (u > v) swap(u, v), swap(r1, r2), swap(c1, c2);

    if (colToBlock[c1] == colToBlock[c2]) {
        unionSet(u, v);
        blockEdges[colToBlock[c1]].push_back({u, v});
    } else {
        bridgeRight[u] = true;
        bridgeLeft[v] = true;
    }
}

void removeEdge(int r1, int c1, int r2, int c2) {
    int u = getCellId(r1, c1), v = getCellId(r2, c2);
    if (u > v) swap(u, v), swap(r1, r2), swap(c1, c2);

    if (colToBlock[c1] == colToBlock[c2]) {
        rebuildBlock(colToBlock[c1], u, v);
    } else {
        bridgeRight[u] = false;
        bridgeLeft[v] = false;
    }
}

bool queryConnectivity(int r1, int c1, int r2, int c2) {
    int startCell = getCellId(r1, c1), endCell = getCellId(r2, c2);
    if (connected(startCell, endCell)) return true;

    queue<BFSState> bfsQueue;
    queue<int> cleanupQueue;
    vector<bool> visited(totalCols * 2 + 5, false);
    
    int startBlock = colToBlock[c1];
    for (int i = 0; i < 4; ++i) {
        if (connected(startCell, corners[startBlock][i])) {
            bfsQueue.push({corners[startBlock][i], startBlock});
        }
    }

    while (!bfsQueue.empty()) {
        BFSState curr = bfsQueue.front();
        bfsQueue.pop();

        if (visited[curr.cellId]) continue;
        visited[curr.cellId] = true;
        cleanupQueue.push(curr.cellId);

        for (int i = 0; i < 4; ++i) {
            if (connected(curr.cellId, corners[curr.blockIdx][i])) {
                if (!visited[corners[curr.blockIdx][i]]) {
                    // Logic to traverse to adjacent blocks via bridges
                    if (i == 0 || i == 2) { // Left corners
                        if (curr.blockIdx > 1 && bridgeLeft[curr.cellId]) {
                            bfsQueue.push({corners[curr.blockIdx - 1][1], curr.blockIdx - 1}); // TR of prev
                            bfsQueue.push({corners[curr.blockIdx - 1][3], curr.blockIdx - 1}); // BR of prev
                        }
                    } else { // Right corners
                        if (curr.blockIdx < numBlocks && bridgeRight[curr.cellId]) {
                            bfsQueue.push({corners[curr.blockIdx + 1][0], curr.blockIdx + 1}); // TL of next
                            bfsQueue.push({corners[curr.blockIdx + 1][2], curr.blockIdx + 1}); // BL of next
                        }
                    }
                }
            }
        }
    }

    int endBlock = colToBlock[c2];
    bool result = false;
    for (int i = 0; i < 4; ++i) {
        if (visited[corners[endBlock][i]] && connected(corners[endBlock][i], endCell)) {
            result = true;
            break;
        }
    }

    while (!cleanupQueue.empty()) {
        visited[cleanupQueue.front()] = false;
        cleanupQueue.pop();
    }

    return result;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    cin >> totalCols;
    initialize();
    
    char operation;
    while (cin >> operation && operation != 'E') {
        int r1, c1, r2, c2;
        cin >> r1 >> c1 >> r2 >> c2;
        
        if (operation == 'O') addEdge(r1, c1, r2, c2);
        else if (operation == 'C') removeEdge(r1, c1, r2, c2);
        else if (operation == 'A') cout << (queryConnectivity(r1, c1, r2, c2) ? "Y\n" : "N\n");
    }
    return 0;
}

Enfoque 2: Árbol de Segmentos para Conectividad de Intervalos

La solución óptima y más elegante utiliza un Árbol de Segmentos para mantener la coenctividad en intervalos de forma eficiente. Cada nodo del árbol almacena la matriz de conectividad entre sus cuatro esquinas: superior izquierda (TL), superior derecha (TR), inferior izquierda (BL) e inferior derecha (BR).

Al fusionar dos intervalos adyacentes, evaluamos las rutas alternativas que cruzan el límite vertical, considerando tanto los puentes horizontales superiores como inferiores. Para responder a una consulta en el intervalo $[l, r]$, extraemos e integramos la información de los segmentos $[1, l]$, $[l, r]$ y $[r, C]$, analizando cómo las esquinas se conectan a través de los límites.

Las actualizaciones de aristas verticales modifican directamente los nodos hoja, mientras que las actualizaciones de aristas horizontales propagan los cambios hacia arriba en el árbol. Este enfoque reduce drásticamente la complejidad temporal.

Complejidad temporal: $O(C \log C)$.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

constexpr int MAX_COLS = 1000005;

bool horizontalEdges[2][MAX_COLS]; 

struct ConnectivityNode {
    int leftCol, rightCol;
    bool leftConn;   // TL-BL
    bool rightConn;  // TR-BR
    bool topConn;    // TL-TR
    bool botConn;    // BL-BR
    bool diag1;      // TL-BR
    bool diag2;      // TR-BL
};

class SegmentTree {
private:
    vector<ConnectivityNode> tree;

    ConnectivityNode merge(const ConnectivityNode& a, const ConnectivityNode& b) {
        ConnectivityNode res;
        res.leftCol = a.leftCol;
        res.rightCol = b.rightCol;

        bool topBridge = horizontalEdges[0][a.rightCol];
        bool botBridge = horizontalEdges[1][a.rightCol];

        res.leftConn = a.leftConn || (a.topConn && topBridge && b.leftConn && botBridge && a.botConn);
        res.rightConn = b.rightConn || (b.topConn && topBridge && a.rightConn && botBridge && b.botConn);
        
        res.topConn = (a.topConn && topBridge && b.topConn) || (a.diag1 && botBridge && b.diag2);
        res.botConn = (a.botConn && botBridge && b.botConn) || (a.diag2 && topBridge && b.diag1);
        
        res.diag1 = (a.topConn && topBridge && b.diag1) || (a.diag1 && botBridge && b.botConn);
        res.diag2 = (a.diag2 && topBridge && b.topConn) || (a.botConn && botBridge && b.diag2);

        return res;
    }

    void build(int p, int l, int r) {
        tree[p].leftCol = l;
        tree[p].rightCol = r;
        if (l == r) {
            tree[p].topConn = tree[p].botConn = true;
            tree[p].leftConn = tree[p].rightConn = false;
            tree[p].diag1 = tree[p].diag2 = false;
            return;
        }
        int mid = (l + r) >> 1;
        build(p << 1, l, mid);
        build(p << 1 | 1, mid + 1, r);
        tree[p] = merge(tree[p << 1], tree[p << 1 | 1]);
    }

    void updateVertical(int p, int col, bool state) {
        if (tree[p].leftCol == tree[p].rightCol) {
            tree[p].leftConn = tree[p].rightConn = state;
            tree[p].diag1 = tree[p].diag2 = state;
            tree[p].topConn = tree[p].botConn = true;
            return;
        }
        int mid = (tree[p].leftCol + tree[p].rightCol) >> 1;
        if (col <= mid) updateVertical(p << 1, col, state);
        else updateVertical(p << 1 | 1, col, state);
        tree[p] = merge(tree[p << 1], tree[p << 1 | 1]);
    }

    void updateHorizontal(int p, int col) {
        if (tree[p].leftCol == tree[p].rightCol) return;
        int mid = (tree[p].leftCol + tree[p].rightCol) >> 1;
        if (col < mid) updateHorizontal(p << 1, col);
        else if (col > mid) updateHorizontal(p << 1 | 1, col);
        tree[p] = merge(tree[p << 1], tree[p << 1 | 1]);
    }

    ConnectivityNode query(int p, int l, int r) {
        if (l <= tree[p].leftCol && tree[p].rightCol <= r) return tree[p];
        int mid = (tree[p].leftCol + tree[p].rightCol) >> 1;
        if (r <= mid) return query(p << 1, l, r);
        if (l > mid) return query(p << 1 | 1, l, r);
        return merge(query(p << 1, l, r), query(p << 1 | 1, l, r));
    }

public:
    SegmentTree(int n) : tree(4 * n + 5) {
        build(1, 1, n);
    }

    void addVerticalEdge(int col) { updateVertical(1, col, true); }
    void removeVerticalEdge(int col) { updateVertical(1, col, false); }
    void toggleHorizontalEdge(int col) { updateHorizontal(1, col); }
    
    ConnectivityNode getInterval(int l, int r) { return query(1, l, r); }
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int totalCols;
    cin >> totalCols;
    
    SegmentTree segTree(totalCols);
    
    char operation;
    while (cin >> operation && operation != 'E') {
        int r1, c1, r2, c2;
        cin >> r1 >> c1 >> r2 >> c2;
        
        if (operation == 'O') {
            if (c1 == c2) segTree.addVerticalEdge(c1);
            else {
                if (c1 > c2) swap(c1, c2);
                horizontalEdges[r1 - 1][c1] = true;
                segTree.toggleHorizontalEdge(c1);
            }
        } else if (operation == 'C') {
            if (c1 == c2) segTree.removeVerticalEdge(c1);
            else {
                if (c1 > c2) swap(c1, c2);
                horizontalEdges[r1 - 1][c1] = false;
                segTree.toggleHorizontalEdge(c1);
            }
        } else if (operation == 'A') {
            if (c1 > c2) {
                swap(r1, r2);
                swap(c1, c2);
            }
            
            ConnectivityNode mid = segTree.getInterval(c1, c2);
            ConnectivityNode left = segTree.getInterval(1, c1);
            ConnectivityNode right = segTree.getInterval(c2, totalCols);
            
            bool ans = false;
            if (r1 == 1 && r2 == 1) {
                ans |= mid.topConn;
                ans |= (left.rightConn && mid.diag2);
                ans |= (mid.diag1 && right.leftConn);
                ans |= (left.rightConn && mid.botConn && right.leftConn);
            } else if (r1 == 2 && r2 == 2) {
                ans |= mid.botConn;
                ans |= (left.rightConn && mid.diag1);
                ans |= (left.rightConn && mid.topConn && right.leftConn);
                ans |= (mid.diag2 && right.leftConn);
            } else if (r1 == 1 && r2 == 2) {
                ans |= mid.diag1;
                ans |= (left.rightConn && mid.diag2 && right.leftConn);
                ans |= (left.rightConn && mid.botConn);
                ans |= (mid.topConn && right.leftConn);
            } else if (r1 == 2 && r2 == 1) {
                ans |= mid.diag2;
                ans |= (left.rightConn && mid.topConn);
                ans |= (mid.botConn && right.leftConn);
                ans |= (left.rightConn && mid.diag1 && right.leftConn);
            }
            cout << (ans ? "Y\n" : "N\n");
        }
    }
    return 0;
}