古人云：时间线段树爽！时间线段树学习笔记。

作者：XiaoQuQu，发表于 Mon Feb 26 2024。

嘛，这个东西虽然叫时间线段树，但是和线段树好像关系并不大，只是借用了一下线段树的结构。

算法介绍

这个算法是用来解决这类问题的：每个操作只在一段时间内生效，然后询问某个时间点所有操作的贡献。

于是我们考虑离线，对整个时间序列建一个线段树，每次操作相当于是在这个线段树上进行了区间修改，所以我们可以利用线段树的结构将他的生效时间分摊到 $O(\log n)$ 个时间区间上。

然后这个东西一般要搭配一些可撤销的数据结构，典中典的就是可撤销并查集。

我们先把所有修改加到这个线段树里，然后整体查询一次，查询的时候，假设我们当前的时间区间是 $[l,r]$，我们就先把当前节点维护的所有操作加到这个可撤销的数据结构里，然后在根节点（或者在某个节点）统计答案，离开这个节点的时候把操作撤销掉。

所以最终插入和查询的复杂度就都是 $O(n\log n)$。

当然如果你有可持久化的数据结构也可以直接用可持久化的数据结构，但有些数据结构不太好可持久化，或者可持久化之后要多一个 $\log$，这个时候就可以用时间线段树。

例题 1：LG5787/BZOJ4025 二分图

题意

给定若干条边，每条边有一个生效区间 $[s,e]$，问在每个时间刻这个图是不是二分图。

题解

并查集判是否为二分图，然后上时间线段树。

怎么并查集判二分图：对于每条边 $u,v$，将 $u,v+n$ 与 $v,u+n$ 合并，如果发现一条边 $u,v$ 在同一个集合中则出现了奇环。

const int MAXN = 2e5 + 5;
int n, m, T, fa[MAXN], sz[MAXN], ans[MAXN];

struct _stck {
	pair<int, int> a[MAXN];
	int __tp;
	void pop() { --__tp; }
	void push(pair<int, int> x) { a[++__tp] = x; }
	int size() { return __tp; }
	auto top() { return a[__tp]; }
} st;

struct _node {
	vector<pair<int, int>> q;
	void addEdge(int u, int v) {
		q.push_back(make_pair(u, v));
	}
} tr[MAXN << 2];

int find(int x) {
	while (fa[x] != x) x = fa[x];
	return x;
}

void merge(int x, int y) {
	if (x == y) return;
	if (sz[x] < sz[y]) swap(x, y);
	fa[y] = x;
	st.push(make_pair(y, sz[x]));
	sz[x] += sz[y];
}

void modify(int p, int l, int r, int L, int R, int u, int v) {
	if (L <= l && r <= R) return tr[p].addEdge(u, v);
	if (L <= mid) modify(lson, l, mid, L, R, u, v);
	if (mid < R) modify(rson, mid + 1, r, L, R, u, v);
}

void undo() {
	auto x = st.top().first, y = st.top().second;
	sz[fa[x]] = y;
	fa[x] = x;
	st.pop();
}

void query(int p, int l, int r) {
	const int top = st.size();
	// add this node's edges
	for (auto [u, v]:tr[p].q) {
		int fu = find(u), fv = find(v);
		if (fu != fv) merge(find(u + n), fv), merge(find(v + n), fu);
		else {
			for (int i = l; i <= r; ++i) ans[i] = 1;
			while ((int)st.size() > top) undo();
			return;
		}
	}
	if (l != r) {
		query(lson, l, mid);
		query(rson, mid + 1, r);
	}
	while ((int)st.size() > top) undo();
}

void work() {
	cin >> n >> m >> T;
	for (int i = 1; i <= 2 * n; ++i) fa[i] = i, sz[i] = 1;
	for (int i = 1, s, e, u, v; i <= m; ++i) {	
		cin >> u >> v >> s >> e;
		modify(1, 1, T, s + 1, e, u, v);
	}
	query(1, 1, T);
	for (int i = 1; i <= T; ++i) cout << (ans[i] ? "No" : "Yes") << endl;
}

例题 2：CF1423H Virus

题意

有 $n$ 个人，给定 $k$，一开始在第一天，有 $q$ 次操作，每次操作形如：

告诉你 $x,y$ 在今天见面了。
查询 $x$ 在过去 $k$ 天与多少人见面（或间接见面）了（包括自己）。
告诉你今天过完了，下一天。

$n,k\le 10^5,q\le 5\times 10^5$。

题解

设当前在第 $t$ 天，考虑操作 $1$，其实影响了 $[t,t+k)$ 这个区间，于是转换为对 $[t,t+k)$ 这个区间的区间修改就做完了。

const int MAXN = 5e5 + 5;
int n, q, k, fa[MAXN], sz[MAXN];

struct _stck {
	pair<int, int> a[MAXN];
	int __tp;
	void pop() { --__tp; }
	void push(pair<int, int> x) { a[++__tp] = x; }
	int size() { return __tp; }
	auto top() { return a[__tp]; }
} st;

int find(int x) {
	while (x != fa[x]) x = fa[x];
	return x;
}

void merge(int x, int y) {
	x = find(x), y = find(y);
	if (x == y) return;
	if (sz[x] < sz[y]) swap(x, y);
	fa[y] = x;
	sz[x] += sz[y];
	st.push(make_pair(x, y));
}

void undo() {
	int x = st.top().first, y = st.top().second;
	fa[y] = y;
	sz[x] -= sz[y];
	st.pop();
}

vector<pair<int, int>> tr[MAXN << 2];
vector<pair<int, int>> qr[MAXN];
int ans[MAXN];

void modify(int p, int l, int r, int L, int R, int x, int y) {
	if (L <= l && r <= R) {
		tr[p].push_back({x, y});
		return;
	}
	if (L <= mid) modify(lson, l, mid, L, R, x, y);
	if (mid < R) modify(rson, mid + 1, r, L, R, x, y);
}

void query(int p, int l, int r) {
	const int top = st.size();
	for (auto [x, y]:tr[p]) merge(x, y);
	if (l == r) {
		for (auto [x, id]:qr[l]) {
			ans[id] = sz[find(x)];
		}
	}
	else query(lson, l, mid), query(rson, mid + 1, r);
	while (st.size() > top) undo();
}

struct _query {
	int op, x, y, t;
} qs[MAXN];

void work() {
	cin >> n >> q >> k;
	for (int i = 1; i <= n; ++i) fa[i] = i, sz[i] = 1;
	int T = 1, t = 0;
	for (int i = 1; i <= q; ++i) {
		int op, x, y;
		cin >> op;
		if (op == 3) ++T;
		if (op == 1) {
			cin >> x >> y;
			qs[++t] = {op, x, y, T};
		}
		if (op == 2) {
			cin >> x;
			qs[++t] = {op, x, i, T};
		}
	}
	qs[t + 1].t = INT_MAX;
	auto getTime = [&](int p) {
		int l = 0, r = t + 1;
		while (l + 1 < r) {
			if (qs[mid].t <= p) l = mid;
			else r = mid;
		}
		return l;
	};
	for (int i = 1; i <= t; ++i) {
		if (qs[i].op == 1) {
			const int endTime = getTime(qs[i].t + k - 1);
			modify(1, 1, q, i, endTime, qs[i].x, qs[i].y);
		}
		if (qs[i].op == 2) {
			qr[i].push_back({qs[i].x, qs[i].y});
		}
	}
	query(1, 1, q);
	for (int i = 1; i <= q; ++i)
		if (ans[i]) cout << ans[i] << endl;
}