强制在线莫队

感觉好牛逼的样子。

在此之前先放一个莫队优化。

奇偶性优化

对于奇数块的右端点递增排序，对于偶数块递减排序。

$10^5$的数据大概可以快$150ms$。

然后才是正文。

强制在线莫队

跟分块没有什么区别，先将序列分成$\sqrt n$块，预处理出每两块之间的信息，然后每次询问找到离它最近的两个端点移动即可。

其实就是在序列上平衡的放$\sqrt n$条路径，这些路径都已经被预处理好了，每次查询时只需要找到曼哈顿距离最近的路径即可。