题解 P5787 【二分图 /【模板】线段树分治】
xht
2019-12-10 19:56:18
## 核心思想
考虑这样一个问题：
- 有一些操作，每个操作只在 $l \sim r$ 的时间段内有效。
- 有一些询问，每个询问某一个时间点所有操作的贡献。
对于这样的询问，我们可以离线后**在时间轴上建一棵线段树**，这样对于每个操作，相当于在线段树上进行区间操作。
遍历整颗线段树，到达每个节点时执行相应的操作，然后继续向下递归，到达叶子节点时统计贡献，回溯时撤销操作即可。
这样的思想被称为**线段树分治**，可以在低时间复杂度内解决一类**在线算法并不优秀**的问题。
#### 【例题】[P5787 二分图 /【模板】线段树分治](https://www.luogu.com.cn/problem/P5787)
首先，图是二分图的充要条件是不存在奇环，这个可以用**扩展域并查集**轻松维护。
按照上述思想建一棵线段树，对于每条边，将它按照线段树区间操作的方式划分成 $\mathcal O(\log k)$ 段，用 `vector` 挂在线段树的节点上。
遍历时，从根节点出发，每到一个节点，将挂在该节点上的所有边合并，然后递归处理左儿子和右儿子。如果发现有某条边合并会出现奇环，那么当前线段树节点所对应的时间区间都不会形成二分图。
当到达叶子节点时，如果合并了所有挂在当前节点上的边，依旧满足二分图的性质，那么可以直接输出 `Yes`。
回溯时，由于并查集不支持删边，我们可以使用**可撤销并查集**，即用一个栈记录下所有对并查集的操作。由于可撤销，因此不能路径压缩，为保证复杂度，必须按秩合并。
总时间复杂度 $\mathcal O(m \log n \log k)$。
```cpp
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;
}
```