CF1774F1 Magician and Pigs (Easy Version) 题解

Cxny · 2022-12-18 14:51:13 · 题解

nb 题。sto \textsf{L\color{red}ittle09} orz。

发现一次 3 操作会重复之前的扣血操作，也即扣血量翻倍。于是出现扣血操作后，不超过 \log(\max x_i) 次 3 操作就会使所有的猪猪 \text{GG}。

先统计出每个 1 操作生成的猪猪到下一个 3 操作之前的实际血量，以及每次 3 操作会给已经在场的猪猪扣多少血。

尝试倒序枚举，统计操作 1 对答案的贡献。

我们维护 sum_i 表示当前生成一只血量为 i 的猪猪，到最后会变成多少只。

对于每个操作 3，若其扣血量没有达到上限，则所有血量大于当前总扣血量的猪猪数量乘 2。

排除并没有扣血的操作 3 后，sum 只会改动 \log 次，大力维护即可。

当前时间复杂度：离线后预处理 O(n)，统计答案时操作 1 O(1)，操作 3 总复杂度 O(m\log X)。

当前空间复杂度：O(\max(n,x))。

其中 X=\max x_i。

代码就不贴了。