题解：P3968 [TJOI2014] 电源插排

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

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

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

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

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

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

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