P14302 基础倍增练习题 6 - 斜二进制倍增

· · 题解

参考：斜二进制倍增。

Update：10.31 更改了之前表述不严谨的地方。

斜二进制倍增

斜二进制倍增，应用在树上问题，可以做到：

原理

像树状数组一样，每个点记录包含自己的一段前缀信息。同时每个点也开一个数组记录自己的信息。

设 x-1 管辖的范围 [l,r]。x 管辖的范围：

声明一些数组：

实现

单点修改：往 tf 跳，不断修改当前点的信息。

区间查询：往 lb 跳。若当前点 x 管辖区间完全包含询问区间，那么用 tr 更新，并跳到 lb。否则用 val 更新，并跳到 x-1。

后缀加点：实现定义即可。

  • 如果 l-1 管辖的区间与 x-1 长度相同，那么 x 就管辖 l-1 管辖的、x-1 管辖的，以及自己的信息；
  • 否则 x 就只管辖自己的信息。

时间复杂度

这里主要讲区间查询的复杂度。

考虑第一次满足 x 管辖区间不完全包含询问区间的时刻 t。

在时刻 t 之前，每次跳跃要么往同级区间跳，要么往上一级区间跳。且跳 O(1) 次同级区间就会往上一级区间跳。

在时刻 t 及之后，每次跳跃要么往同级区间跳，要么往下一级区间跳。且跳 O(1) 次同级区间就会往下一级区间跳。

两部分时间复杂度都是 O(\log n)，故单次查询的时间复杂度为 O(\log n)。

树上问题

可以很好迁移。具体的，用每个点的深度（根结点深度为 1）来之前区间问题中的下标 x。每个点相当于维护从祖先到自己这一条树链的信息。

发现某两条树链的信息若有交，那么交的这一部分信息可以共用。

实现时将区间问题的 x-1 换作树上问题的 fa 即可。

树上 LCA

两个点中，深度大的点先跳到和深度小的点同级的位置，然后再两个点同时向上跳跃。

树链信息

深度较浅的点跳到 LCA 的深度，深度较深的点跳到 LCA 深度加 1 的深度。将两部分拼起来即可。

题解

题目：P14302 基础倍增练习题 6。

一开始 n 个带点权的孤立点。每次操作要么是连边，要么查询树链点权的最大子段和。 n 和询问次数 \le 3\times 10^6。强制在线。内存 512 MB。

发现树链剖分不能处理在线连边，ST 表式倍增内存会爆。所以可以用斜二进制倍增。

下面默认 n 和 m 同阶。

每次连边时，考虑将 size 小的那一边的每一个点加到 size 大的那一边。启发式合并均摊是 O(n\log n) 的。调用动态加点函数即可。每一次加点是 O(1) 的，这部分是 O(n \log n) 的。

每次查询，两边分别往上跳，跳到 LCA 的位置，并把沿途信息记录下来。这一部分也是 O(n \log n)。

所以总体是 O(n \log n) 的。瓶颈在于查询时向上跳时信息合并，这里常数会比较大。

代码

最大子段和部分：

struct Max_Seq {
    LL vl, vr, va, sum;
    Max_Seq(LL vl, LL vr, LL va, LL sum):
        vl(vl), vr(vr), va(va), sum(sum) {}
    Max_Seq() {}
    friend Max_Seq operator + (const Max_Seq & a,const Max_Seq & b) {
        return Max_Seq(
            max(a.vl, a.sum + b.vl),
            max(b.vr, b.sum + a.vr),
            max({a.va,b.va,a.vr + b.vl}),
            a.sum + b.sum
        );
    }
}tr[N], val[N];

Max_Seq get_rev(Max_Seq x) {
    return Max_Seq(x.vr, x.vl, x.va, x.sum);
}

斜二进制的部分：

int fa[N], dth[N], tf[N], lb[N];

void push_up(int x) {
    int p = fa[x];
    if (p == lb[x]) {
        tr[x] = val[x];
    } else {
        tr[x] = (val[x] + tr[p]) + tr[lb[p]];
    }
}

void append(int cu, int pa) {
    int p = pa, q = lb[p], r = lb[q];
    if (q == 0 || dth[p] - dth[q] != dth[q] - dth[r]) {
        lb[cu] = pa;
    } else {
        tf[p] = tf[q] = cu;
        lb[cu] = r;
    }
    push_up(cu);
}

int get_lca(int x, int y) {
    if (dth[x] > dth[y]) {
        swap(x, y);
    }
    while (dth[y] > dth[x]) {
        int p = lb[y];
        if (dth[p] <= dth[x] - 1) {
            y = fa[y];
        } else {
            y = p;
        }
    }
    while (x != y) {
        if (lb[x] != lb[y]) {
            x = lb[x], y = lb[y];
        } else {
            x = fa[x], y = fa[y];
        }
    }
    return x;
}

查询部分：

Max_Seq get_seq(int cu, int d) {
    Max_Seq ans = Max_Seq(-inf, 0, -inf, 0);
    while (dth[cu] >= d) {
        int p = lb[cu];
        if (dth[p] < d - 1) {
            ans = ans + val[cu];
            cu = fa[cu];
        } else {
            ans = ans + tr[cu];
            cu = p;
        }
    }
    return ans;
}

LL query(int x, int y) {
    int lca = get_lca(x, y);
    if (x == y) return val[x].va;
    if (dth[x] > dth[y]) swap(x, y);
    Max_Seq p1 = get_seq(x, dth[lca]);
    Max_Seq p2 = get_seq(y, dth[lca] + 1);
    return (p1 + get_rev(p2)).va;
}

连边部分：（其中 B 是并查集结构体）

void dfs(int cu, int pa) {
    dth[cu] = dth[pa] + 1;
    fa[cu] = pa; //注意先更新再 append
    append(cu, pa);
    for (int to: e[cu]) {
        if (to == pa) continue;
        dfs(to, cu);
    }
}

void unite(int x, int y) {
    int tx = B.bcj(x), ty = B.bcj(y);
    if (B.sz[tx] < B.sz[ty]) swap(tx, ty), swap(x, y);
    dfs(y, x);
    e[x].pb(y);
    e[y].pb(x);
    B.merge(x, y);
}