题解：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))。

提交记录