题解：P13984 数列分块入门 9

· · 题解

先离散化。

首先有一个很简单的做法，那就是直接莫队冲。

但是我们注意到有一题叫 P4168 [Violet] 蒲公英 是这道题的在线版，也可以用这个做。

这里介绍一下回滚莫队的做法。

对于 l,r 在同一块的询问，直接暴力。

剩下的询问按左端点的块排序，处理一块内的询问时，先记录下当前 r 的信息，然后移动左端点，每次进入下一个询问的时候回退一下信息版本，注意同一块的右端点要单调递增，这样每次只会移动左端点。

复杂度 O(n\sqrt n)。