首先想到冰山的生长,如果我们不停的让 X_i 为 10^9,那么冰山数量一下子就会超过 10^{18},然后炸掉,所以我们可以想到使用二元组去维护冰山,一个二元组 {(x,y)} 表示大小为 x 的冰山有 y 个,但是想到还是会炸,所以我们维护的时候就可以实时对 y 取模。\
所以算法就比较清晰了,我们用一个 map 去维护这些二元组,然后记录一个 sum 表示 {(x,y)} 实际上是表示的 x+sum 的冰山有 y 个,那么我们每一次操作就可以分类讨论,如果 X \le -1,就只用从 map 的最左边一直弹出被融化掉的冰山,即满足 x+sum+X \le 0 的二元组,同理,如果 X \ge 1,那么就判断 x+sum+X 是否比 k 大,如果比 k 大,那么就自然要分裂了,注意每一次记得取模。
时间复杂度
首先一开始的 n 是少不了了,然后看每一次的冰川的分裂情况,如果 X 是负数,那么冰川的数量就会减少,相较于后面的处理时间复杂度就会相应地减少。如果 X 是正的,那么最坏情况就是分裂出来了 1,k,x+X 这三种冰川,依然是线性的,所以最后的时间复杂度就是 (n + m)\times \log_2n。