做法很简单，然而写起来一堆坑..
#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;
}