作用
处理一些加边删边问题。
实现
不知道为啥叫线段树分治,不如叫时间线段树。
如果一条边 \(e\) 在 \(l\) 时刻加入 \(r\) 时刻删除,那么可以看成在 \([l,r)\) 的时刻内都有这条边。
考虑用线段树维护时刻,给线段树上每个区间维护一个 vector
,里面存覆盖了这个区间的边。
然后询问时就在线段树上递归,每次把这个区间的边加进一个数据结构中,当离开这个区间时,把这个区间中的边给撤销。
所以维护边的数据结构要支持撤销,一般使用可撤销并查集。
题目
【模板】线段树分治
首先先把题目的 \(l\) 时刻出现,\(r\) 时刻删除变成在 \([l+1,r]\) 时刻内出现。
考虑如何快速判定二分图,可以考虑扩展域并查集,也就是维护两个集合 \(S\)、\(T\),每次添加一条边 \((u,v)\),若这两个点属于相同的集合,那么就不是二分图。
有了这个,对时间开一棵线段树,再用可撤销并查集维护边即可。
代码
#include <bits/stdc++.h>void Freopen() {freopen("", "r", stdin);freopen("", "w", stdout);
}using namespace std;
const int N = 2e5 + 10, M = 2e5 + 10, inf = 1e9, mod = 998244353;int n, m, K;struct DSU {int fa[N], siz[N], n;vector< pair< int, int> > del;DSU() {}DSU( int _n) {n = _n; del.clear();for ( int i = 1; i <= n; i ++) siz[i] = 1, fa[i] = i;}int find( int x) {return x == fa[x] ? x : find(fa[x]);}int merge( int u, int v) {u = find(u), v = find(v);if (u == v) return 0;if (siz[u] < siz[v]) swap(u, v);del.push_back({u, v});siz[u] += siz[v], fa[v] = u;return 1;}void Del() {if (! del.size()) return ;auto [u, v] = del.back(); del.pop_back();siz[u] -= siz[v], fa[v] = v;}
} D;vector< pair< int, int> > tr[N * 4];void ins( int x, int y, pair< int, int> e, int k = 1, int l = 1, int r = K) {if (x > y) return ;if (x <= l && r <= y) return tr[k].push_back(e), void();int mid = (l + r) >> 1;if (x <= mid) ins(x, y, e, k << 1, l, mid);if (y > mid) ins(x, y, e, k << 1 | 1, mid + 1, r);
}void solve( int k = 1, int l = 1, int r = K) {int tot = 0; // tot 表示这个区间加了多少边for ( auto [u, v] : tr[k]) {if (D.find(u) == D.find(v)) {for ( int i = l; i <= r; i ++)cout << "No\n";while (tot --) D.Del();return ;}tot += D.merge(u, v + n);tot += D.merge(u + n, v);}if (l == r) {cout << "Yes\n";while (tot --) D.Del();return ;}int mid = (l + r) >> 1;solve(k << 1, l, mid), solve(k << 1 | 1, mid + 1, r);while (tot --) D.Del();
}signed main() {ios :: sync_with_stdio(false);cin.tie(0), cout.tie(0);cin >> n >> m >> K;D = DSU(2 * n);for ( int i = 1; i <= m; i ++) {int x, y, l, r;cin >> x >> y >> l >> r;l ++;ins(l, r, make_pair(x, y));}solve();return 0;
}