线段树分治 学习笔记

线段树的一个小应用

核心思想

考虑这样一个问题：

• 有一些操作，每个操作只在 $l \sim r$ 的时间段内有效。
• 有一些询问，每个询问某一个时间点所有操作的贡献。

对于这样的询问，我们可以离线后在时间轴上建一棵线段树，这样对于每个操作，相当于在线段树上进行区间操作。

遍历整颗线段树，到达每个节点时执行相应的操作，然后继续向下递归，到达叶子节点时统计贡献，回溯时撤销操作即可。

这样的思想被称为线段树分治，可以在低时间复杂度内解决一类在线算法并不优秀的问题。

【例题】P5787 二分图 /【模板】线段树分治

首先，图是二分图的充要条件是不存在奇环，这个可以用扩展域并查集轻松维护。

按照上述思想建一棵线段树，对于每条边，将它按照线段树区间操作的方式划分成 $\mathcal O(\log k)$ 段，用 vector 挂在线段树的节点上。

遍历时，从根节点出发，每到一个节点，将挂在该节点上的所有边合并，然后递归处理左儿子和右儿子。如果发现有某条边合并会出现奇环，那么当前线段树节点所对应的时间区间都不会形成二分图。

当到达叶子节点时，如果合并了所有挂在当前节点上的边，依旧满足二分图的性质，那么可以直接输出 Yes。

回溯时，由于并查集不支持删边，我们可以使用可撤销并查集，即用一个栈记录下所有对并查集的操作。由于可撤销，因此不能路径压缩，为保证复杂度，必须按秩合并。

总时间复杂度 $\mathcal O(m \log n \log k)$。

const int N = 1e5 + 7, M = 2e5 + 7;
int n, m, k, u[M], v[M], f[N<<1], d[N<<1];
struct T {
	int l, r;
	vi e;
} t[N<<2];
stack< pi > s;

void build(int p, int l, int r) {
	t[p].l = l, t[p].r = r;
	if (l == r) return;
	build(ls, l, md), build(rs, md + 1, r);
}

void ins(int p, int l, int r, int x) {
	if (t[p].l >= l && t[p].r <= r) return t[p].e.pb(x), void();
	if (l <= md) ins(ls, l, r, x);
	if (r > md) ins(rs, l, r, x);
}

inline int get(int x) {
	while (x ^ f[x]) x = f[x];
	return x;
}

inline void merge(int x, int y) {
	if (x == y) return;
	if (d[x] > d[y]) swap(x, y);
	s.push(mp(x, d[x] == d[y])), f[x] = y, d[y] += d[x] == d[y];
}

void dfs(int p, int l, int r) {
	bool ok = 1;
	ui o = s.size();
	for (ui i = 0; i < t[p].e.size(); i++) {
		int x = t[p].e[i], u = get(::u[x]), v = get(::v[x]);
		if (u == v) {
			for (int j = l; j <= r; j++) prints("No");
			ok = 0;
			break;
		}
		merge(get(::u[x] + N), v), merge(get(::v[x] + N), u);
	}
	if (ok) {
		if (l == r) prints("Yes");
		else dfs(ls, l, md), dfs(rs, md + 1, r);
	}
	while (s.size() > o) d[f[s.top().fi]] -= s.top().se, f[s.top().fi] = s.top().fi, s.pop();
}

int main() {
	rd(n), rd(m), rd(k), build(1, 1, k);
	for (int i = 1, l, r; i <= m; i++) {
		rd(u[i]), rd(v[i]), rd(l), rd(r);
		if (l ^ r) ins(1, l + 1, r, i);
	}
	for (int i = 1; i <= n; i++) f[i] = i, f[i+N] = i + N;
	dfs(1, 1, k);
	return 0;
}

参考资料

• FlashHu 线段树分治总结（线段树分治，线段树，并查集，树的dfn序，二分图染色）
• lvmaooi 线段树分治概述