LOJ121 「离线可过」动态图连通性

做法很简单，然而写起来一堆坑..

#include <assert.h>
#include <algorithm>
#include <cstdio>
#include <iostream>
#include <vector>
using int_t = long long int;
using std::cin;
using std::cout;
using std::endl;
const int_t LARGE = 1e6;
const int_t INF = 0x7fffffff;
// const int_t
struct State {
    int_t val;
    int_t id;
    State operator+(const State& state) const {
        if (val < state.val) return *this;
        return state;
    }
};
struct Query {
    int_t v1, v2, id;
};
struct Edge {
    int_t from, to, id;
};
struct Node {
    int_t id = -2;
    Node* chds[2] = {nullptr, nullptr};
    Node*& left;
    Node*& right;
    Node* parent = nullptr;
    State state, val;
    Edge edge;
    bool flipped = false;
    Node(int_t id) : left(chds[0]), right(chds[1]) {
        this->state.id = id;
        this->state.val = INF;
        this->val = state;
    }
    void updateFrom(Node* node) {
        node->parent = this;
        val = val + node->val;
    }
    void maintain() {
        val = state;
        if (left) updateFrom(left);
        if (right) updateFrom(right);
    }
    int_t chdOf() const {
        if (parent == nullptr) return -1;
        if (this == parent->left) return 0;
        if (this == parent->right) return 1;
        return -1;
    }
    void flip() {
        flipped ^= 1;
        std::swap(left, right);
    }
    void pushDown() {
        if (flipped) {
            flipped = false;
            if (left) left->flip();
            if (right) right->flip();
        }
    }
};
void rotate(Node* node) {
    Node* Pr = node->parent;
    Pr->pushDown();
    node->pushDown();
    int_t side = node->chdOf();
    int_t sidep = Pr->chdOf();
    Node* Gr = Pr->parent;
    Pr->chds[side] = node->chds[side ^ 1];
    node->chds[side ^ 1] = Pr;
    node->parent = Gr;
    Pr->maintain();
    node->maintain();
    if (Gr && sidep != -1) {
        Gr->chds[sidep] = node;
        Gr->maintain();
    }
}
bool isAuxRoot(Node* node) {
    if (node == nullptr || node->parent == nullptr) return true;
    return node->chdOf() == -1;
}
void splay(Node* node) {
    assert(node);
    static Node* stack[LARGE + 1];
    int_t top = 0;
    Node* curr = node;
    while (true) {
        stack[top++] = curr;
        if (isAuxRoot(curr)) break;
        curr = curr->parent;
    }
    while (top) stack[--top]->pushDown();
    while (isAuxRoot(node) == false) {
        if (isAuxRoot(node->parent))
            rotate(node);
        else {
            if (node->chdOf() == node->parent->chdOf()) {
                rotate(node->parent);
            } else {
                rotate(node);
            }
            rotate(node);
        }
    }
}
void access(Node* node) {
    Node* last = nullptr;
    while (node) {
        splay(node);
        node->right = last;
        last = node;
        node->maintain();
        node = node->parent;
    }
}
Node* getRoot(Node* node) {
    access(node);
    splay(node);
    while (true) {
        node->pushDown();
        if (node->left == nullptr) break;
        node = node->left;
    }
    return node;
}
void changeRoot(Node* node) {
    access(node);
    splay(node);
    node->flip();
}
void link(Node* n1, Node* n2) {
    changeRoot(n2);
    access(n1);
    splay(n1);
    n1->pushDown();
    n1->right = n2;
    n1->maintain();
}
void cut(Node* n1, Node* n2) {
    changeRoot(n1);
    access(n2);
    splay(n1);
    n1->right = nullptr;
    n2->parent = nullptr;
    n1->maintain();
}
State query(Node* n1, Node* n2) {
    changeRoot(n1);
    access(n2);
    splay(n2);
    return n2->val;
}
int_t mat[5001][5001];
int n, m;
std::vector<Edge> edges;
std::vector<Query> querys;

int main() {
    // freopen("graph4.in", "r", stdin);
    static Node* nodes[LARGE + 1];
    scanf("%d%d", &n, &m);
    for (int_t i = 1; i <= n; i++) {
        nodes[i] = new Node(-1);
        nodes[i]->id = i;
    }
    for (int_t i = 1; i <= m; i++) {
        int opt, v1, v2;
        scanf("%d%d%d", &opt, &v1, &v2);
        if (v1 > v2) std::swap(v1, v2);
        if (opt == 0) {
            edges.push_back(Edge{v1, v2});
            edges.back().id = i;
            mat[v1][v2] = edges.back().id;
            nodes[n + edges.back().id] = new Node(edges.back().id);
            nodes[n + edges.back().id]->id = n + i;
            nodes[n + edges.back().id]->edge = edges.back();
        } else if (opt == 1) {
            nodes[n + mat[v1][v2]]->state.val = i;
            nodes[n + mat[v1][v2]]->maintain();
        } else {
            querys.push_back(Query{v1, v2, i});
        }
    }
    const auto pushEdge = [&](const Edge& edge) {
        if (getRoot(nodes[edge.from]) == getRoot(nodes[edge.to])) {
            State state = query(nodes[edge.from], nodes[edge.to]);
            //点的出现时间也是INF，避免把普通的点当成代表边的点
            if (state.val >= nodes[n + edge.id]->val.val) return;
            Node* oldEdge = nodes[n + state.id];
            // cut错边了！！
            cut(nodes[oldEdge->edge.from], oldEdge);
            cut(nodes[oldEdge->edge.to], oldEdge);
        }
        Node* currEdge = nodes[n + edge.id];
        link(nodes[edge.from], currEdge);
        link(nodes[edge.to], currEdge);
    };
    int_t pos = 0;
    for (const auto& query : querys) {
        while (pos < edges.size() && edges[pos].id < query.id) {
            pushEdge(edges[pos]);
            pos++;
        }
        Node *n1 = nodes[query.v1], *n2 = nodes[query.v2];
        if (getRoot(n1) != getRoot(n2)) {
            printf("N\n");
        } else if (::query(n1, n2).val < query.id) {
            printf("N\n");
        } else {
            printf("Y\n");
        }
    }
    return 0;
}