历史研究
历史研究
思路
考虑到维护最大值的话，删除操作不太方便，我们考虑回滚莫队。
我们对于左端点在一个块内的情况一起处理，分两类讨论：
- 右端点也和左端点在一个块内，那么直接暴力即可，然后再重做一遍清空。复杂度 \(O(\sqrt n)\)。
- 右端点在另一边，此时右端点方向我们按照正常莫队的方法，而对于在块内的，我们还是暴力。正常莫队复杂度就是 \(O(n\sqrt n)\)，再加一个暴力一次 \(\sqrt n\)。
题目中询问与序列长度同阶，所以复杂度 \(O(n\sqrt n)\)。
注意需要离散化。