线段树分治 学习笔记

作者: xht37 分类: 笔记 发布时间: 2019-12-10 18:04

Visits: 982

线段树的一个小应用

核心思想

考虑这样一个问题:

  • 有一些操作,每个操作只在 $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;
}

参考资料

2条评论
  • Kylin

    2020年10月12日 上午11:13

    请问可以在我的博客中引用吗?如果可以引用请您授权,谢谢!

    1. xht37

      2020年10月16日 上午12:17

      可以

发表评论

电子邮件地址不会被公开。 必填项已用*标注