P4666 Growing Trees 题解

· · 题解

Start

前置知识：树状数组

区间修改，单点查询。

 

1.思路

看到各个大佬们用的都是 FHQ、Splay、权值线段树等高级数据结构，我自愧弗如。

但是我可以用简单基本的算法吊打：树状数组。

现在所有通过的程序中，最优解速度第 4（没有开 O2，快读等优化），空间 & 码量都是最小的。

 

2.建树

根据差分，树状数组 b_i=a_i-a_{i-1}，先把 a_i 数组排序，然后依次单点修改：add(i, a[i] - a[i - 1])。但是我们在查询中就会有一个问题：我们无法知道 \min 和 \max 在 b 这个不下降数组的位置？于是我们写两个二分函数 left(x) 和 right(x)。

left：查询 sum(i) >= x 时 i 的最大值，即最后一个前缀和 \ge x 的位置。

right：查询 sum(i) <= x 时 i 的最小值，即第一个前缀和 \le x 的位置。

这两个函数在修改中必不可少。

 

3.修改

查询很简单，前面说了，考虑如何修改。

修改最重要的就是有一些高度相同的树，只有一部分修改，另一部分不修改（样例第一个输出），如何处理？

假设修改操作的两个输入分别是 x,y，那么我们先算出找到要修改的数的值得区间 [x,s]，s = sum(x + left(y) - 1)，很好理解。

接下来分成两段处理，一段是值在 [x,s-1] 中的，另一段是值为 s 的。具体代码：

const int z(left(y)), s(sum(x + z - 1)), l(left(s)), r(right(s));
add(z, 1), add(l, -1);
add(l + r - x - z + 1, 1), add(r + 1, -1);

 

End

特判：

  1. 查询的范围在 a 中最大值与最小值之外
  2. 需要修改的数的数量大于符合范围的数的数量

代码