RT, MLE on #1, #2, #3, #6, #14

提交记录

Code:

#include <bits/stdc++.h>
using namespace std;

template <class T>
class persistent_array {
private:
	struct node {
		T val;
		node *left, *right;
		
		node() : left(nullptr), right(nullptr) {}
		node(const T& v) : val(v), left(nullptr), right(nullptr) {}
	};
	
	void build(const T* arr, int l, int r, node*& rt) {
		if (l > r) return;
		if (l == r) {
			rt = new node(arr[l]); 
			return;
		}
		rt = new node();
		int mid = (l + r) >> 1;
		build(arr, l, mid, rt->left);
		build(arr, mid + 1, r, rt->right);
	}
	
	static node* clone(node* rt) {
		node* res = new node();
		res->left = rt->left, res->right = rt->right;
		return res;
	}
	
	void update(int x, const T val, int l, int r, node*& rt, node* pre) {
		if (l > r) return;
		rt = clone(pre);
		if (l == r) {
			rt->val = val;
			return;
		}
		int mid = (l + r) >> 1;
		if (x <= mid) update(x, val, l, mid, rt->left, pre->left);
		else update(x, val, mid + 1, r, rt->right, pre->right);
	}
	
	T query(int x, int l, int r, node* rt) const {
		if (l > r) return 0;
		if (l == r) return rt->val;
		int mid = (l + r) >> 1;
		if (x <= mid) return query(x, l, mid, rt->left);
		return query(x, mid + 1, r, rt->right);
	}
	
	int n;
	vector<node*> root;
	
public:
	persistent_array() {root.push_back(nullptr);} 
	persistent_array(const T* arr, int _n) {init(arr, _n);}
	persistent_array(const T* begin, const T* end) {init(begin, end);}
	
	void init() {
		for (node*& cur : root) delete cur;
		root.clear();
		root.emplace_back(nullptr);
	}
	void init(const T* arr, int _n) {
		n = _n, init();
		build(arr, 1, n, root[0]);
	}
	void init(const T* begin, const T* end) {
		n = end - begin, init();
		build(begin, 1, n, root[0]);
	}
	
	void reserve_root(std::size_t s) {root.reserve(s);}
	size_t version_size() const {return root.size();}
	
	T update(int version, int idx, const T& val) {
		root.emplace_back(nullptr);
		update(idx, val, 1, n, root.back(), root[version]);
		return val;
	}
	
	T at(int version, int idx) const {
		return query(idx, 1, n, root[version]);
	}
	
	void copy(int version, int to) {
		node* cpy = clone(root[version]);
		root[to] = cpy;
	}
	void save(int version) {
		root.emplace_back(nullptr);
		copy(version, root.size() - 1);
	}
	
	void create() {root.emplace_back(nullptr);}
	void erase(int version) {root.erase(root.begin() + version);}
};

class persistent_unionfind {
private:
	int n;
	persistent_array<int> fa, sz;
	
	int find(int version, int k) const {
		while (fa.at(version, k) != k) k = fa.at(version, k);
		return k;
	}
	
public:
	persistent_unionfind() {}
	explicit persistent_unionfind(int _n) {init(_n);}
	
	inline void init(int _n) {
		n = _n;
		int _fa[n + 1], _sz[n + 1];
		for (int i = 1; i <= n; i++) _sz[i] = 1, _fa[i] = i;
		fa.init(_fa, n), sz.init(_sz, n);
	}
	
	void unite(int version, int x, int y) {
		x = find(version, x), y = find(version, y);
		if (x == y) {
			fa.save(version), sz.save(version);
			return;
		}
		int tot = sz.at(version, x) + sz.at(version, y);
		if (sz.at(version, x) > sz.at(version, y)) {
			fa.update(version, y, x);
			sz.update(version, x, tot);
		} else {
			fa.update(version, x, y);
			sz.update(version, y, tot);
		}
	}
	
	bool connected(int version, int x, int y) const {
		return find(version, x) == find(version, y);
	}
	
	void save(int version) {
		fa.save(version), sz.save(version);
	}
	void copy(int version, int to) {
		fa.copy(version, to), sz.copy(version, to);
	}
	
	size_t version_size() {return fa.version_size();}
	void reverse(size_t n) {fa.reserve_root(n), sz.reserve_root(n);}

	void create() {fa.create(), sz.create();}
	void erase(int version) {fa.erase(version), sz.erase(version);}
};

int n, q;
int opt, a, b, x;

persistent_unionfind uf;

namespace FastIO { 
	// INT_MIN会出错
	template <typename T>
	inline void read(T& x) {
		x = 0; int t = 1; char ch = getchar();
		for (; ch < '0' || ch > '9'; ch = getchar()) if (ch == '-') t = -1;
		for (; '0' <= ch && ch <= '9'; ch = getchar()) x = (x << 1) + (x << 3) + (ch ^ 48);
		x *= t;
	}
	
	template <typename T>
	inline void write(T x) {
		if (x < 0) putchar('-'), x = -x;
		static int st[40];
		int top = 0;
		do {
			st[top++] = x % 10;
			x /= 10;
		} while (x);
		while (top) putchar(st[--top] ^ 48);
	}
	
	template <typename T>
	inline void writeln(const T x) {write(x), putchar('\n');}
	template <typename T>
	inline void writesp(const T x) {write(x), putchar(' ');}
	
	template <typename T, typename... Args>
	inline void read(T& t, Args&... args) {
		read(t); read(args...);
	}
	
	template <typename T>
	inline void write(const char c, const T x) {
		write(x), putchar(c);
	}
	template <typename T, typename... Args>
	inline void write(T t, const char c, Args... args) {
		read(c, t); read(c, args...);
	}
}
using namespace FastIO;

int main() {
	read(n, q);
	uf.init(n);
	uf.reverse(q + 2);
	for (int v = 1; v <= q; v++) {
		uf.save(v - 1);
		read(opt);
		if (opt == 2) {
			read(x);
			uf.copy(x, v);
		} else {
			read(a, b);
			if (opt == 1) {
				uf.unite(v, a, b);
				uf.erase(v);
			} else {
				writeln((int) uf.connected(v, a, b));
			}
		}
	}
	return 0;
}