---
tags: codebook
---

# Time segment tree

**problem:** [TIOJ 1903](https://tioj.ck.tp.edu.tw/problems/1903)

constexpr int maxn = 5e5 + 5;
V<P<int>> arr[(maxn + 1) << 2];
V<int> dsu, sz;
V<tuple<int, int, int>> his;
int cnt, q;
int find(int x) {
	return x == dsu[x] ? x : find(dsu[x]);
};
inline bool merge(int x, int y) {
	int a = find(x), b = find(y);
	if (a == b) return false;
	if (sz[a] > sz[b]) swap(a, b);
	his.emplace_back(a, b, sz[b]), dsu[a] = b, sz[b] += sz[a];
	return true;
};
inline void undo() {
	auto [a, b, s] = his.back(); his.pop_back();
	dsu[a] = a, sz[b] = s;
}
#define m ((l + r) >> 1)
void insert(int ql, int qr, P<int> x, int i = 1, int l = 0, int r = q) {
	// debug(ql, qr, x); return;
	if (qr <= l || r <= ql) return;
	if (ql <= l && r <= qr) {arr[i].push_back(x); return;}
	if (qr <= m)
		insert(ql, qr, x, i << 1, l, m);
	else if (m <= ql)
		insert(ql, qr, x, i << 1 | 1, m, r);
	else {
		insert(ql, qr, x, i << 1, l, m);
		insert(ql, qr, x, i << 1 | 1, m, r);
	}
}
void traversal(V<int>& ans, int i = 1, int l = 0, int r = q) {
	int opcnt = 0;
	// debug(i, l, r);
	for (auto [a, b] : arr[i])
		if (merge(a, b))
			opcnt++, cnt--;
	if (r - l == 1) ans[l] = cnt;
	else {
		traversal(ans, i << 1, l, m);
		traversal(ans, i << 1 | 1, m, r);
	}
	while (opcnt--)
		undo(), cnt++;
	arr[i].clear();
}
#undef m
bool rit(int& ret) {
	ret = 0; bool b = false; char c = cin.rdbuf()->sbumpc();
	while (!isdigit(c)) {
		if (c == EOF)
			return false;
		b = (c == '-' ? true : b);
		c = cin.rdbuf()->sbumpc();
	}
	while (isdigit(c))
		ret = ret * 10 + c - '0', c = cin.rdbuf()->sbumpc();
	ret = b ? -ret : ret;
	return true;
}
void wit(int x) {
	if (!x) cout.rdbuf()->sputc('0');
	char tmp[10]; int cnt = 0; bool b = false;
	if (x & numeric_limits<int>::min()) 
		tmp[cnt++] = -(x % 10) + '0', x /= -10, b = true;
	while (x) tmp[cnt++] = x % 10 + '0', x /= 10;
	if (b) cout.rdbuf()->sputc('-');
	while (cnt--) cout.rdbuf()->sputc(tmp[cnt]);
}
inline void solve() {
	int n, m; rit(n), rit(m), rit(q);
	dsu.resize(cnt = n), sz.assign(n, 1);
	iota(dsu.begin(), dsu.end(), 0);
	// a, b, time, operation
	UM<ll, V<int>> s;
	for (int i = 0; i < m; i++) {
		int a, b; rit(a), rit(b);
		if (a > b) swap(a, b);
		s[((ll)a << 32) | b].emplace_back(0);
	}
	for (int i = 0; i < q; i++) {
		char c; int a, b;
		cin >> c, rit(a), rit(b);
		if (a > b) swap(a, b);
		switch (c) {
		case 'N':
			s[((ll)a << 32) | b].push_back(i);
			break;
		case 'D':
			auto tmp = s[((ll)a << 32) | b].back();
			s[((ll)a << 32) | b].pop_back();
			insert(tmp, i, P<int> {a, b});
		}
	}
	for (auto [p, v] : s) {
		int a = p >> 32, b = p & -1;
		while (v.size()) {
			insert(v.back(), q, P<int> {a, b});
			v.pop_back();
		}
	}
	V<int> ans(q);
	traversal(ans);
	for (auto i : ans)
		wit(i), cout.rdbuf()->sputc('\n');
}

**problem:** [CF 813F](https://codeforces.com/contest/813/problem/F)

constexpr int maxn = 1e5 + 5;
V<V<int>> e;
V<P<int>> arr[(maxn + 1) << 2];
V<int> dsu, sz;
bool cur = true;
V<tuple<int, int, int>> his;
int find(int x) {return x == dsu[x] ? x : find(dsu[x]);}
bool merge(int x, int y) {
	int a = find(x), b = find(y);
	if (a == b) return false;
	if (sz[a] > sz[b]) swap(a, b);
	his.emplace_back(a, b, sz[b]);
	dsu[a] = b, sz[b] += sz[a];
	return true;
}
void undo() {
	auto [a, b, s] = his.back();
	his.pop_back();
	dsu[a] = a, sz[b] = s;
}
#define m ((l + r) >> 1)
void insert(int ql, int qr, P<int> op, int i = 1, int l = 0, int r = maxn) {
	if (qr <= l || r <= ql) return;
	if (ql <= l && r <= qr) {arr[i].push_back(op); return;}
	insert(ql, qr, op, i << 1, l, m), insert(ql, qr, op, i << 1 | 1, m, r);
}
void traversal(V<bool>& ans, int i = 1, int l = 0, int r = maxn) {
	if ((int)ans.size() <= l) return;
	int opcnt = 0;
	for (auto [a, b] : arr[i]) {
		if (find(a) == find(b))
			cur = false;
		else {
			for (auto p : e[a])
				if (merge(p, b)) opcnt++;
			for (auto p : e[b])
				if (merge(a, p)) opcnt++;
		}
		e[a].push_back(b), e[b].push_back(a);
	}
	if (!cur || r - l == 1) {
		for (int k = l; k < r; k++)
			ans[k] = cur;
	} else {
		traversal(ans, i << 1, l, m);
		traversal(ans, i << 1 | 1, m, r);
	}
	cur = true;
	while (opcnt--) undo();
	for (auto [a, b] : arr[i])
		e[a].pop_back(), e[b].pop_back();
}
#undef m
inline void solve() {
	int n, q, a, b; cin >> n >> q;
	e.assign(n, V<int>());
	dsu.resize(n), sz.assign(n, 1);
	iota(dsu.begin(), dsu.end(), 0);
	UM<ll, int> m;
	for (int i = 0; i < q; i++) {
		cin >> a >> b, a--, b--;
		if (a > b) swap(a, b);
		if (m.count(((ll)a << 32) | b)) {
			auto prev = m[((ll)a << 32) | b];
			insert(prev, i, P<int> {a, b});
			m.erase(((ll)a << 32) | b);
		} else
			m[((ll)a << 32) | b] = i;
	}
	for (auto [p, i] : m) {
		int a = p >> 32, b = p & -1;
		insert(i, q, P<int> {a, b});
	}
	V<bool> ans(q);
	traversal(ans);
	for (int i = 0; i < q; i++)
		cout << V<string> {"NO", "YES"} [ans[i]] << endl;
}