洛谷P5247 动态图完全连通性 ETT解法

#include <iostream>
#include <unordered_map>
#include <unordered_set>
#include <stack>
#include <cassert>

using namespace std;

#define MAXN 5011
#define MAX_LEVEL 15

struct ETT {
	int c[2 * MAXN][2], fa[2 * MAXN];
	int ori[MAXN * 2];
	// node[v][u] is the occurrence of v after u.
	// Corresponds to the directed edge from u to v.
	// If u is the parent of v, then it is the first occurrence of v.
	// i.e., if u is the parent of v, then uv is the first occurrence of v,
	// vu is the last occurrence of v.
	unordered_map<int, int> node[MAXN];
	stack<int> free_list;
	int tot;

	int subtree_size[MAXN * 2];
	// Only the representative occurrence could be the tag.
	int representative[MAXN];
	struct Tag {
		// Only stores edges of this level.
		unordered_set<int> edges;
		int tag;
	} tag_tree[MAXN * 2], tag_non_tree[MAXN * 2];

	void update_tag(Tag tags[], int x) {
		if (!tags[x].edges.empty()) {
			tags[x].tag = x;
		} else if (tags[ls(x)].tag) {
			tags[x].tag = tags[ls(x)].tag;
		} else if (tags[rs(x)].tag) {
			tags[x].tag = tags[rs(x)].tag;
		} else {
			tags[x].tag = 0;
		}
	}
	void reassign_representative(int& rt, int x) {
		int u = ori[x];
		if (x != representative[u])
			return;
		int y = node[u].begin()->second;
		assert(x != y);
		splay(y);
		representative[u] = y;
		swap(tag_non_tree[x].edges, tag_non_tree[y].edges);
		update_tag(tag_non_tree, y);
		swap(tag_tree[x].edges, tag_tree[y].edges);
		update_tag(tag_tree, y);
		rt = y;
	}
	std::unordered_set<int> take_out_edges(Tag type[], int x) {
		assert(x == representative[ori[x]]);
		splay(x);
		auto tmp = std::unordered_set<int>();
		swap(tmp, type[x].edges);
		update_tag(type, x);
		return std::move(tmp);
	}
	void give_edges(Tag type[], int x, unordered_set<int> edges) {
		assert(x == representative[ori[x]]);
		splay(x);
		swap(edges, type[x].edges);
		update_tag(type, x);
	}
	void add_directed_edge(Tag type[], int u, int v) {
		int x = representative[u];
		if (type[x].edges.empty()) {
			splay(x);
			type[x].edges.insert(v);
			update_tag(type, x);
		} else {
			type[x].edges.insert(v);
		}
	}
	void delete_directed_edge(Tag type[], int u, int v) {
		int x = representative[u];
		if (type[x].edges.size() == 1) {
			splay(x);
			type[x].edges.erase(v);
			update_tag(type, x);
		} else {
			type[x].edges.erase(v);
		}
	}
	void new_tree_edge(int u, int v) {
		link_new(u, v);
		add_directed_edge(tag_tree, u, v);
		add_directed_edge(tag_tree, v, u);
	}

	inline int& ls(int rt) {
		return c[rt][0];
	}
	inline int& rs(int rt) {
		return c[rt][1];
	}
	inline int side(int x) {
		return x == rs(fa[x]);
	}
	void pushup(int x) {
		update_tag(tag_tree, x);
		update_tag(tag_non_tree, x);
		subtree_size[x] = subtree_size[ls(x)] + subtree_size[rs(x)] + 1;
	}
	// pushup(x) later
	void __rotate_up(int x) {
		int y = fa[x], z = fa[y], side_x = side(x), w = c[x][side_x ^ 1];
		fa[x] = z;
		if (z)
			c[z][side(y)] = x;
		if (w)
			fa[w] = y;
		c[y][side_x] = w;
		fa[y] = x;
		c[x][side_x ^ 1] = y;
		pushup(y);
	}
	void splay(int x, int to = 0) {
		while (fa[x] != to) {
			int y = fa[x];
			if (fa[y] != to)
				__rotate_up(side(x) == side(y) ? y : x);
			__rotate_up(x);
		}
		pushup(x);
	}

	int new_node() {
		int x;
		if (!free_list.empty()) {
			x = free_list.top();
			free_list.pop();
		} else {
			x = ++tot;
		}
		return x;
	}
	void del_node(int x) {
		free_list.push(x);
	}

	int __find_min_or_max(int rt, bool mx) {
		while (c[rt][mx])
			rt = c[rt][mx];
		return rt;
	}
	int find_min_or_max(int rt, bool mx) {
		rt = __find_min_or_max(rt, mx);
		splay(rt);
		return rt;
	}

	void __concat(int rt_x, int rt_y) {
		node[ori[rt_y]][ori[rt_x]] = rt_y;
		rs(rt_x) = rt_y;
		fa[rt_y] = rt_x;
		pushup(rt_x);
	}
	void concat(int& rt_x, int& rt_y) {
		rt_x = find_min_or_max(rt_x, true);
		rt_y = find_min_or_max(rt_y, false);
		__concat(rt_x, rt_y);
	}
	void __append_node(int& rt_x, int y, int u) {
		rt_x = find_min_or_max(rt_x, true);
		ls(y) = rs(y) = 0;
		ori[y] = u;
		tag_tree[y].tag = tag_non_tree[y].tag = 0;
		subtree_size[y] = 1;
		__concat(rt_x, y);
	}
	inline void append_node(int& rt_x, int u) {
		__append_node(rt_x, new_node(), u);
	}
	// aAuBa, a is the original root
	// Return the splay root(Not the tree root)
	int make_root(int u) {
		int x = node[u].begin()->second; // Any occurrence
		splay(x);
		int y = __find_min_or_max(x, false);
		if (ori[y] == u)
			return x; // Already root
		fa[ls(x)] = 0;
		ls(x) = 0;
		node[u][0] = x;
		// pushup(x);
		// y: aA, x: uBa
		splay(y);
		node[ori[y]].erase(0);
		int tmp = y;
		y = rs(y);
		// y: A
		if (y) {
			fa[y] = 0;
			concat(x, y);
		}
		// x: uBaA
		reassign_representative(x, tmp);
		__append_node(x, tmp, u);
		// x: uBaAu
		return x;
	}

	void init(int n) {
		for (int i = 1; i <= n; ++i) {
			int x = new_node();
			ls(x) = rs(x) = fa[x] = 0;
			ori[x] = i;
			node[i][0] = x;
			representative[i] = x;
			subtree_size[x] = 1;
		}
	}
	inline void access(int x) {
		splay(x);
	}
	int find_root(int x) {
		// If not splay, the complexity is definitely wrong.
		// Suppose it is a chain, and we always find_root(last_node)
		splay(x);
		return find_min_or_max(x, false);
	}
	void link_new(int u, int v) {
		int x = node[u].begin()->second; // Any occurrence
		int y = make_root(v);
		append_node(y, u);
		splay(x);
		int x2 = rs(x);
		y = find_min_or_max(y, false);
		node[ori[y]].erase(0);
		__concat(x, y);
		if (x2) {
			fa[x2] = 0;
			concat(x, x2);
		}
	}
	void cut_existing(int u, int v) {
		make_root(u); // To make sure that u is the father of v
		int uv = node[v][u];
		node[v].erase(u);
		node[v][0] = uv;
		auto vu = node[u][v];
		node[u].erase(v);
		splay(vu);
		splay(uv, vu);
		int x = ls(uv);
		fa[x] = 0;
		ls(uv) = 0;
		pushup(uv); // Necessary?
		fa[uv] = 0;
		// ls(vu) = 0;
		int y = rs(vu);
		if (y) {
			fa[y] = 0;
			// rs(vu) = 0;
			concat(x, y);
		}
		reassign_representative(x, vu);
		del_node(vu);
	}
	bool is_connected(int u, int v) {
		if (u == v)
			return true;
		int x = node[u].begin()->second;
		splay(x);
		int y = node[v].begin()->second;
		splay(y);
		return fa[x] == y || fa[fa[x]] == y;
	}
};

struct DynamicConnectivity {
	ETT F[MAX_LEVEL];
	unordered_map<int, unordered_map<int, int> > level;
	void init(int n) {
		for (int i = 0; (1 << i) <= n; ++i)
			F[i].init(n);
	}
	// Assume no duplicate edge
	void link_new(int u, int v) {
		level[u][v] = 0;
		level[v][u] = 0;
		if (F[0].is_connected(u, v)) {
			F[0].add_directed_edge(F[0].tag_non_tree, v, u);
			F[0].add_directed_edge(F[0].tag_non_tree, u, v);
		} else {
			F[0].new_tree_edge(u, v);
		}
	}
	bool reconnect(int u, int v, int l) {
		int x = F[l].node[u].begin()->second;
		int y = F[l].node[v].begin()->second;
		F[l].access(x);
		F[l].access(y);
		if (F[l].subtree_size[x] > F[l].subtree_size[y])
			swap(x, y);
		while (1) {
			F[l].access(x);
			int xx = F[l].tag_tree[x].tag;
			if (xx == 0)
				break;
			int u = F[l].ori[xx];
			auto tmp = F[l].take_out_edges(F[l].tag_tree, xx);
			for (int v : tmp) {
				F[l].delete_directed_edge(F[l].tag_tree, v, u);
				F[l+1].new_tree_edge(u, v);
				++level[u][v];
				++level[v][u];
			}
		}

		y = F[l].find_root(y);
		while (1) {
			F[l].access(x);
			int xx = F[l].tag_non_tree[x].tag;
			if (xx == 0)
				break;
			auto tmp = F[l].take_out_edges(F[l].tag_non_tree, xx);
			int u = F[l].ori[xx];
			do {
				auto it = tmp.begin();
				int v = *it;
				int yy = F[l].node[v].begin()->second;
				tmp.erase(it);
				F[l].delete_directed_edge(F[l].tag_non_tree, v, u);
				if (F[l].find_root(yy) == y) {
					if (!tmp.empty())
						F[l].give_edges(F[l].tag_non_tree, xx, std::move(tmp));
					for (int i = 0; i < l; ++i)
						F[i].link_new(u, v);
					F[l].new_tree_edge(u, v);
					return true;
				} else {
					F[l+1].add_directed_edge(F[l+1].tag_non_tree, u, v);
					F[l+1].add_directed_edge(F[l+1].tag_non_tree, v, u);
					++level[u][v];
					++level[v][u];
				}
			} while (!tmp.empty());
		};
		return false;
	}
	void cut_existing(int u, int v) {
		auto it1 = level[u].find(v);
		int l = it1->second;
		level[u].erase(it1);
		level[v].erase(u);

		auto& s = F[l].tag_non_tree[F[l].representative[u]].edges;
		if (s.find(v) != s.end()) {
			F[l].delete_directed_edge(F[l].tag_non_tree, u, v);
			F[l].delete_directed_edge(F[l].tag_non_tree, v, u);
			return;
		}
		F[l].delete_directed_edge(F[l].tag_tree, u, v);
		F[l].delete_directed_edge(F[l].tag_tree, v, u);
		for (int i = 0; i <= l; ++i)
			F[i].cut_existing(u, v);
		while (1) {
			if (reconnect(u, v, l))
				break;
			if (l == 0)
				break;
			--l;
		}
	}
	bool is_connected(int u, int v) {
		return F[0].is_connected(u, v);
	}
};

int main() {
	int n, m;
	static DynamicConnectivity dc;

	scanf("%d%d", &n, &m);
	dc.init(n);
	int last = 0;
	while (m--) {
		int op, x, y;
		scanf("%d%d%d", &op, &x, &y);
		x ^= last;
		y ^= last;
		switch (op) {
		case 0:
			dc.link_new(x, y);
			break;
		case 1:
			dc.cut_existing(x, y);
			break;
		case 2:
			if (dc.is_connected(x, y)) {
				puts("Y");
				last = x;
			} else {
				puts("N");
				last = y;
			}
			break;
		}
	}

	return 0;
}