CF1060G Balls and Pockets

我一来就想二分，然后发现 consider it backwards 可以把二分去掉，发现需要找到 $h_{cur}\le x + cur$ 最大的 $cur$，这个东西是单调的，于是得到了 $O(qn)$​ 的做法。

剩下的时间一直在尝试离线下来一起操作，用尽力气得到了一个很多细节的平衡树维护 id 的做法。

最后的最后，重新 consider it forwards 发现一个树状数组就搞定了。

记录一下最后 consider it forwards 的细节：

考虑极远处 $L = 10^{18}$ 有一个区间 $[L, L + n)$，不断对这个区间进行操作发现恰好能够不重不漏覆盖 $[a_1, L]$，并且每次操作的覆盖是一个区间。

小于 $< a_i$ 的询问是平凡的。

对于一个询问，假如 $t$ 次操作后包含了 $x$，那么就是要求当前位置在 $t - k$ 次操作后所在的位置。

这个直接模拟就好了。

需要用一个数据结构支持单点修改查询前缀和查询第 $k$ 个非 $0$ 位置，这个直接树状数组维护。

时间复杂度 $O(n\log n)$。

后记：感觉直接看题解很难想到，但是从我模拟赛时 consider it backwards 的角度出发优化，发现这样做需要把一个区间从中间剖开插入一个新的位置，这样维护就很烦，这时候再倒着做就是 consider it forwards 的做法了，也就是思维过程其实是倒着做 $2$ 次。