P1110 [ZJOI2007] 报表统计
考虑到操作 MIN_SORT_GAP 比较简单，用一个 set 维护前驱后继即可，重点关注 INSERT，MIN_GAP。
发现我们可以先开一个单链表来存储所有数，开数组表示原数列的第 \(i\) 个元素现在的位置。每次插入只需要在对应位置插入，然后更新数组的值。
关于维护最小差值，用一个堆，删除操作可以开一个删除堆，将删除的数放入，每次获取堆顶如果删除堆中也是堆顶则一直弹出。
复杂度 \(O(n+m\log(n+m)\)。
[ZJOI2007]报表统计
发布时间 2023-08-11 15:11:28作者: wscqwq