题意

你要维护一张\(n\)个点的无向简单图。你被要求执行\(m\)条操作，加入删除一条边及查询两个点是否连通。

• 0：加入一条边。保证它不存在。
• 1：删除一条边。保证它存在。
• 2：查询两个点是否联通。

\(n \leq 5\times 10^3, m \leq 5\times 10^5\)

题解

第一次写按时间分治的题，感觉还是比较 清新 有趣的

对时间建线段树，一个结点\([l, r]\)上存储在时间\([l, r]\)上存在的边集，那么询问在叶子结点上

对这颗线段树\(dfs\)，我们到一个结点就把边连起来（用并查集），可是需要回溯（即我们要把边撤销）。值得庆幸的是可以发现每次撤销的是当前最后一次加入的，所以使用按秩合并并查集就好。

复杂度：\(O(m \log n)\)

#include <algorithm>

#include <cstdio>

#include <vector>

#include <map>

using namespace std;

#define fs first

#define sc second

#define pb push_back

typedef pair<int, int> P;

const int N = 5e5 + 10;

const int M = 5010;

int n, m, Map[M][M], qs[N], qsum[N];

vector<P> edge, q, T;

bool ans[N];

struct Edge {

	int v, nxt;

} e[N * 35];

int hd[N << 2], c;

void push_edge(int id, int rt) {

	e[++ c] = (Edge) {id, hd[rt]}; hd[rt] = c;

}

void add(int u, int l, int r, int ql, int qr, int id) {

	if(l == ql && r == qr) { push_edge(id, u); return ; }

	int mid = (l + r) >> 1;

	if(qr <= mid) add(u << 1, l, mid, ql, qr, id);

	else if(ql > mid) add(u << 1 | 1, mid + 1, r, ql, qr, id);

	else {

		add(u << 1, l, mid, ql, mid, id);

		add(u << 1 | 1, mid + 1, r, mid + 1, qr, id);

	}

}

int nq, f[M], sz[M], st[N], top;

int find(int u) {

	return u == f[u] ? u : find(f[u]);

}

void dfs(int u, int l, int r) {

	if(qsum[r] == qsum[l - 1]) return ;

	int ntop = top;

	for(int i = hd[u]; i; i = e[i].nxt) {

		int u = find(edge[e[i].v].fs), v = find(edge[e[i].v].sc);

		if(u != v) {

			if(sz[u] < sz[v]) st[++ top] = u, f[u] = v, sz[v] += sz[u];

			else st[++ top] = v, f[v] = u, sz[u] += sz[v];

		}

	}

	if(l == r) {

		if(qs[l]) qs[l] --, ans[qs[l]] = find(q[qs[l]].sc) == find(q[qs[l]].fs);

	} else {

		int mid = (l + r) >> 1;

		dfs(u << 1, l, mid);

		dfs(u << 1 | 1, mid + 1, r);

	}

	while(top > ntop) {

		int u = st[top --];

		sz[f[u]] -= sz[u];

		f[u] = u;

	}

}

int main() {

	scanf("%d%d", &n, &m);

	for(int i = 1; i <= m; i ++) {

		int op, x, y, tmp;

		scanf("%d%d%d", &op, &x, &y);

		if(x > y) swap(x, y);

		if(op == 0) {

			if(!Map[x][y]) {

				int id = (int) edge.size();

				Map[x][y] = id + 1;

				edge.pb(P(x, y));

				T.pb(P(i, m));

			}

		}

		if(op == 1) {

			if(tmp = Map[x][y]) {

				T[tmp - 1].sc = i;

				Map[x][y] = 0;

			}

		}

		if(op == 2) { qs[i] = (int) q.size() + 1; q.pb(P(x, y)); }

		qsum[i] = qsum[i - 1] + qs[i];

	}

	for(int i = 0; i < edge.size(); i ++) {

		add(1, 1, m, T[i].fs, T[i].sc, i);

	}

	for(int i = 1; i <= n; i ++) f[i] = i, sz[i] = 1;

	dfs(1, 1, m);

	for(int i = 0; i < q.size(); i ++) puts(ans[i] ? "Y" : "N");

	return 0;

}