线段树分治 学习笔记
Visits: 1110
线段树的一个小应用
Contents
hide
核心思想
考虑这样一个问题:
- 有一些操作,每个操作只在 $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 线段树分治概述
Kylin
2020年10月12日 上午11:13
请问可以在我的博客中引用吗?如果可以引用请您授权,谢谢!
xht37
2020年10月16日 上午12:17
可以