集训队互测2018 完美的队列

· · 题解

谔谔，感觉做的时候被牵着鼻子走了。

对于每次操作，求出最晚的全部被剔除的时间，然后对于每种数拿出来求区间并即可。考虑分块，整块的询问是简单的，你可以双指针。假设目前你要求 i 时刻加入的在某个块 [L,R] 中的最晚时间，记录 t_x 代表位置 x 还需要加入多少个，一开始 t_x=a_x。变量 mx=\max_{x\in [L,R]} t_x 代表最多需要加入多少个数。遍历后面所有的加入，如果完全包含就打 tag。否则遍历散块然后更新每个点 t，重构整个块。一旦标记不小于 mx，就说明此时弹空了。这样做的复杂度是 O(\frac{nq}{b}+qb)。

对于散块询问，容易变成 O(qb) 次单点询问。把所有位置 x 的散块加入搞出来，在这个序列上面双指针，我们需要维护的就是某一段时间内某个整块被加入了多少次。可以 O(\frac{n^2}{b}) 空间预处理。但是我们不想要大空间，其实这个过程还是可以逐个块去做，于是离线就好了。取 b=\sqrt{n}，总的复杂度是 O(n\sqrt{n})。

代码咕了。

/bx @华山抡剑

好像是可以 poly log：blog。

polylog 没什么区别嘛，注意到一个可能有点反直觉可能也不反直觉的事实，每个线段树的子树中所有操作的数量的和是 O(n\log n) 的。然后对于每个线段树上的节点暴力扫他整个子树双指针就好了。