警告

本 Blog 仅供蒟蒻 tiger0132 复习用。本蒟蒻

不对其内容正确性做任何保证。

若发现 Bug 请在评论区反馈。本蒟蒻欢迎一切形式的贡献。

点击屏幕以关闭。

「ZJOI 2019」线段树 - 线段树

题意

传送门:洛谷 P5280 - 线段树

你要维护一堆区间 \([1, n]\) 的线段树,最开始只有一棵树,而且是空的。支持两种操作:

  1. 把这堆线段树翻倍,把第 \(i\) 棵复制成 \(2i\)\(2i+1\),并给所有编号为奇数的线段树中的区间 \([l, r]\) 打上 lazy tag。
  2. 查询所有的线段树中打上 lazy tag 的节点数。

解法

首先约定操作的区间为 \([L, R]\),节点的区间为 \([l, r]\),目前正在进行第 \(i, (i \ge 1)\) 次区间修改。

考虑每次区间修改对 tag 的影响。对于每次操作,我们可以将点分为 \(5\) 类:

  1. 被访问过且被 pushdown 的点。即满足 \([L, R] \subseteq [l, r]\) 的点。这种点的数量为 \(O(\log n)\) 级别。
  2. 被访问过且被修改 lazy tag 的点。即满足 \([l, r] \subseteq [L, R]\)被访问过的点。这种点的数量也是 \(O(\log n)\) 级别。
  3. 没被访问过,但是被 pushdown 影响的点。即满足 \([l, r] \subsetneq [L, R]\)被访问过的点。这种点的数量还是 \(O(\log n)\) 级别。
  4. \(2\) 类点子树中的点(不含第 \(2\) 类点)。即满足 \([l, r] \subseteq [L, R]\)没被访问过的点。这种点的数量是 \(O(n)\) 级别。
  5. \(3\) 类点子树中的点(不含第 \(3\) 类点)。即满足 \([l, r] \subsetneq [L, R]\)没被访问过的点。这种点的数量也是 \(O(n)\) 级别。

然后令 \(f\) 为当前点在所有线段树中 tag 的和,并讨论区间修改对这 \(5\) 种节点的影响:

  1. 此类点的 tag 一定为 \(0\)。即 \(f\) 不变。
  2. 此类点的 tag 一定为 \(1\)。即 \(f \leftarrow f + 2^{i-1}\)
  3. 如果它某个祖先的 tag 为 \(1\),那么它为 \(1\)

其中第 \(4, 5\) 类点的 \(f\) 不受影响。即 \(f \leftarrow 2f\)

接下来考虑第 \(3\) 类点。如果令当前点存在 tag 为 \(1\) 的祖先的线段树数为 \(g\),那么有 \(f \leftarrow f + g\)

所以我们又需要维护 \(g\) 了……继续分类讨论:

  1. 此类点的 \(g\) 一定为 \(0\)。即 \(g\) 不变。
  2. 此类点的 \(g\) 一定为 \(1\)。即 \(g \leftarrow g + 2^{i-1}\)
  3. 此类点的 \(g\) 也不受影响,即 \(g \leftarrow 2g\)
  4. 此类点的 \(g\) 也不受影响,即 \(g \leftarrow 2g\)
  5. 此类点的 \(g\) 一定为 \(1\)。即 \(g \leftarrow g + 2^{i-1}\)

那么答案为整棵树的 \(f\) 的和。

注意到第 \(4, 5\) 类点的数量是 \(O(n)\) 级别的,而且难以维护,所以要魔改式子。

令整棵树的 \(f\) 的和乘 \(2^i\) 为答案。即令 \(f\) 为当前点 tag 为 \(1\) 的概率,\(g\) 为令当前点存在 tag 为 \(1\) 的祖先的概率。然后重新推式子:

  1. \(f \leftarrow \frac f2\)
  2. \(f \leftarrow \frac{f+1}2\)
  3. \(f \leftarrow \frac{f+g}2\)

其中第 \(4, 5\) 类点 \(f\) 不变。

同时推出 \(g\) 的式子:

  1. \(g \leftarrow \frac g2\)
  2. \(g \leftarrow \frac{g+1}2\)
  3. \(g\) 不变。
  4. \(g\) 不变。
  5. \(g \leftarrow \frac{g+1}2\)

注意到第 \(5\) 类点的 \(g\) 可以用 \(O(\log n)\) 个 lazy tag 维护,所以直接线段树维护就好了。

用 lazy tag 维护 lazy tag!

代码