Offline Dynamic Connectivity

#include <cstdio>

#include <algorithm>
#include <limits>
#include <map>

using namespace std;

const int N = 5010, M = 500010;

struct Data {
    int v, id;

    Data() {}

    Data(int v, int id) : v(v), id(id) {}

    bool operator<(const Data& rhs) const {
        return v < rhs.v;
    }
};

struct LCT {
    struct Node {
        bool rev;
        Data val, myn;
        union {
            struct {
                Node *ls, *rs;
            };
            Node* ch[2];
        };
        Node *prt, *path;

        bool relation() const {
            return this == prt->rs;
        }

        void pushDown() {
            if (rev) {
                rev = false;
                swap(ls, rs);
                if (ls)
                    ls->rev = !ls->rev;
                if (rs)
                    rs->rev = !rs->rev;
            }
        }

        void update() {
            myn = val;
            if (ls)
                myn = min(myn, ls->myn);
            if (rs)
                myn = min(myn, rs->myn);
        }

        void rotate() {
            if (prt->prt)
                prt->prt->pushDown();
            prt->pushDown();
            pushDown();
            path = prt->path;
            prt->path = NULL;
            bool f = relation();
            Node* p = prt;
            if (p->prt)
                p->prt->ch[p->relation()] = this;
            prt = p->prt;
            p->ch[f] = ch[!f];
            if (ch[!f])
                ch[!f]->prt = p;
            ch[!f] = p;
            p->prt = this;
            p->update();
            update();
        }

        void splay() {
            while (prt) {
                if (!prt->prt)
                    return rotate();
                prt->prt->pushDown();
                prt->pushDown();
                if (relation() == prt->relation()) {
                    prt->rotate();
                    rotate();
                } else {
                    rotate();
                    rotate();
                }
            }
        }

        void expose() {
            splay();
            pushDown();
            if (rs) {
                rs->path = this;
                rs->prt = NULL;
                rs = NULL;
                update();
            }
        }

        bool splice() {
            splay();
            if (!path)
                return false;
            path->expose();
            path->rs = this;
            prt = path;
            path = NULL;
            prt->update();
            return true;
        }

        void access() {
            expose();
            while (splice());
        }

        void evert() {
            access();
            splay();
            rev = !rev;
        }

        Data query() {
            access();
            splay();
            return myn;
        }
    };

    Node ver[N * 2 + M];

    void link(int u, int v) {
        ver[u].evert();
        ver[u].path = ver + v;
    }

    void cut(int u, int v) {
        ver[u].evert();
        ver[v].access();
        ver[u].expose();
        ver[v].path = NULL;
    }

    Data query(int u, int v) {
        ver[u].evert();
        return ver[v].query();
    }
};

int n, m, vCnt;
LCT mst;
int opt[M], x[M], y[M], lst[M];
int eu[N * 2 + M], ev[N * 2 + M];
map<int, int> g[N];

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; ++i) {
        scanf("%d%d%d", &opt[i], &x[i], &y[i]);
    }
    for (int i = m; i; --i) {
        if (x[i] > y[i])
            swap(x[i], y[i]);
        if (opt[i] == 1)
            g[x[i]][y[i]] = i;
        else if (opt[i] == 0) {
            map<int, int>::iterator it = g[x[i]].find(y[i]);
            if (it == g[x[i]].end())
                lst[i] = numeric_limits<int>::max();
            else {
                lst[i] = it->second;
                g[x[i]].erase(it);
            }
        }
    }
    for (int i = 1; i <= n; ++i)
        mst.ver[i].val = mst.ver[i].myn = Data(numeric_limits<int>::max(), i);
    vCnt = n;
    for (int i = 2; i <= n; ++i) {
        ++vCnt;
        mst.ver[vCnt].val = mst.ver[vCnt].myn = Data(0, vCnt);
        mst.link(1, vCnt);
        mst.link(vCnt, i);
        eu[vCnt] = 1;
        ev[vCnt] = i;
    }
    for (int i = 1; i <= m; ++i) {
        if (x[i] > n || y[i] > n) {
            fputs("WA", stderr);
            fprintf(stderr, "%d %d %d\n", i, x[i], y[i]);
            return 0;
        }
        if (opt[i] == 2) {
            Data gt = mst.query(x[i], y[i]);
            puts(gt.v > i ? "Y" : "N");
        } else if (opt[i] == 0) {
            Data gt = mst.query(x[i], y[i]);
            if (gt.v >= lst[i])
                continue;
            ++vCnt;
            mst.cut(gt.id, eu[gt.id]);
            mst.cut(gt.id, ev[gt.id]);
            mst.ver[vCnt].val = mst.ver[vCnt].myn = Data(lst[i], vCnt);
            mst.link(vCnt, x[i]);
            mst.link(vCnt, y[i]);
            eu[vCnt] = x[i];
            ev[vCnt] = y[i];
        }
    }
    return 0;
}