Luogu5068 [Ynoi2015] 我回来了

题意：对于集合 ，进行以下操作 :

• 每轮操作将 中的数全部减 （常数），并删除所有 的数。

• 若某一轮减完后，没有 的数，则停止操作。

定义 为上述过程持续的轮数。

维护集合 ，支持下列操作 ：

• 向 中插入数 。

• 查询 的值。

允许离线，，，时限 。

---

对于每个 ，将值域 分为 块，询问相当于查询有值的极长块前缀的长度。

总块数是 的。

由于只有插入，有值的极长块前缀单调增长。

每次插入只需快速找出新增的有值的块，然后尝试极长块前缀，在树状数组上单点修改。树状数组的复杂度为均摊 。

接下来考虑如何求新增的有值的块。

注意到允许离线，问题可以转化为求每个块第一次有值的时间。

记 为 第一次被插入的时间，使用 ST 表即可做到 。

综上，时间复杂度为 ，空间复杂度为 ，且常数较小。