题解：P3968 [TJOI2014] 电源插排

KidA · 2025-04-20 11:23:54 · 题解

区间问题，优先考虑线段树，O(q \log n) 的时间复杂度可以承受。

具体的，我们维护五条信息：

• 区间内被使用插排个数 used。

• 区间内的左端最长连续空插排 lmx。

• 区间内的右端最长连续空插排 rmx。

• 区间内的最长连续空插排 mx。

• 区间内的最长连续空插排的中间位置 m。

在 pushup 中，used 可以直接加，lmx,rmx,mx,m 套路地更新即可。

对于同学的到来 / 离去，我们使用一个 map 存储其插排的位置并进行单点修改即可。

但是，普通线段树一般需要开 4N 空间，但此题无法承受，于是我们使用动态开点线段树即可。

值得注意的是，因为同学们总会选右边的，所以 pushup 时需要从右至左地更新 mx,m，具体见代码。

综上，本题让我们学会了线段树处理区间问题的常见思路（维护 lmx,rmx），以及通过使用动态开点线段树节省空间。