题解：CF1060G Balls and Pockets

NOIP 模拟赛做到这个题，被创飞了。

第一反应是二分答案正序模拟，但是发现二分继续优化唯一途径是整体二分，而答案值域为 $O(nk)$，不可优化。

考虑倒序模拟，可以把序列划分为若干段，第 $i$ 段进行倒序模拟一轮后会加上 $i-1$。

还是不好优化，考虑这些区间有什么性质。

跳段问题考虑先把询问跳到第一个跨过当前段的位置，以缩减信息规模。

这样做完后，每个点在所处段（记为第 $id$ 个段）的第 $[1,id-2]$ 个位置，记这些点再跳到下一个段的次数是 $v$，容易发现，由于这些点下标差严格小于 $id$，所以不同点 $v$ 的极差不超过 $1$，且取值单调，把点按位置分为两部分 $A,B$，进一步的，经过一轮模拟后，$A,B$ 点的大小关系交换。

考虑直接使用文艺平衡树维护这个操作，具体地我们需要实现按值分裂，子树加减，找出 $<0$ 的位置。

前两个操作是平凡的，找出 $<0$ 的位置可以维护子树 $\min$ 后直接暴力，和势能线段树复杂度分析本质相同，总复杂度 $O((n+m)\log (n+m))$。