23.5 杂题

CF543E Listening to Music

先稍微转换问题，对于所有 \(a_i<x\)，相当于给所有 \(\in [i,\min(i+m-1,n)]\) 的右端点答案加一。最后就是求一个区间 \(\min\)。于是有一个离线扫描线的 \(n\log n\) 做法。可持久化+标记永久化，可以做到 \(O(n\log n)\) 时空。考虑分块。

对于散块询问，我们需要知道的是块首的值。如果直接预处理是 \(O(n\sqrt{n})\) 空间的。考虑继续平衡复杂度，对操作继续分块。那么就相当于有 \(O(\sqrt{n})\) 个区间加，做一次区间查 \(\min\)。差分一下复杂度就平衡下来了。

对于整块查询，由于整块加法是平凡的，我们只需考虑散块加法。而对于一个修改，散块加法只有 \(O(1)\) 次。于是在修改的时候对散块重构，重新记录散块的 \(\min\) 即可。