「JOISC 2016 Day 2」雇佣计划 题解

__vector__ · 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