偶然遇到的一些均摊趣题

1. CF1774F1

考虑一个 repeat 操作发生了甚么：

假设现在全局一共扣除了 \(m\) 的血量，现在所拥有的猪的集合 \(S\)

那么操作相当于把所有 \(S\) 中的猪的血量去掉 \(m\) 扔进 \(S\) 来

看似每次数量翻倍，其实不然！

如果发生了一次 reduce 操作，那么经过 log 次 repeat，当前的 \(m\) 就会达到 \(2 \times 10^5\)，这个 repeat 相当于啥也没干。

这是突破口。设计算法方面，谨慎选择 DS。

考虑维护下标桶 \(A\) 数组。

对于 opt1: \(A_{x}\) 增加 \(1\)。
对于 opt2: 全局减 \(x\)。
对于 opt3:

1.如果目前 \(m=0\)，那么全局 \(\times 2\)。
2.如果 \(m \ge 2 \times 10^5\)，那么不动。
3.否则，暴力执行 repeat 操作。

如果使用一种巧妙的 map 维护方法：对于全局减 \(x\)，使用偏移量；但是因此我们需要大值域的 \(\text{map}\)。但是关于全局 \(\times 2\)，我们需要使用一个标记，实现细节较多，注意出现 reduce 操作后处理掉所有标记，然后从此再不使用标记，因为我们的标记可能在实现过程中没有跟着偏移，也导致时间复杂度多 \(\log\)。代码细节看 code。

如果使用平衡树，那么是裸题。动态开点 sgt 同理。