本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2023-10-19 16:45:45

Sol

题目本质是设置一个数值下限，选中数组中数值下限以上的所有数，将连在一起的被选中数视作一个连通块，求连通块数量。

先离散化一遍把数据范围从 $10^9$ 降到 $4 \cdot10^5$。

先预处理能力下限为 $i$ 的答案，并用数据结构维护。

重点是如何维护。

• 设能力下限是 $lim$

• 设一次操作中，操作位置 $pos$，新数是 $d$，原数是 $old$。

• 对于 $d \ge old$：

• 在 $lim = [old+1,d]$ 的所有情况中，原来位置 pos 不会被选中，而现在会被选中。

• 那么这个变化如何对 $lim = [old+1,d]$ 的情况们造成影响呢？

• 情况 1，位置 $pos-1,pos+1$ 都被选中：

• 连通块个数 -1。

• 情况 2，位置 $pos-1,pos+1$ 只有一个被选中：

• 连通块个数不变。

• 情况 3，位置 $pos-1,pos+1$ 都没有被选中：

• 连通块个数 +1.

• 分别计算情况 $1,3$ 对应的 $lim$ 区间，它们与 $[old+1,d]$ 分别的交就分别是 $1,3$ 情况的影响的 $lim$ 区间。

• 然后更新受影响区间的答案。

• 对于 $d \le old$：

• 和 $d \ge old$ 差不多。

可以发现是区间修改单点查询，使用树状数组即可。

Submission