题目描述：给出一个长度为\(n\)的数组，每次询问区间 \([l,r]\)，求 \(\max\limits_{x}x*cnt_x\)，其中 \(cnt_x\) 表示 \(x\) 在区间 \([l,r]\) 的出现次数。
数据范围：\(n\le 10^5,a_i\le 10^9\)。
分块也可以做到 \(O(n\sqrt{n})\)，但是空间也是 \(O(n\sqrt{n})\)。使用回滚莫队可以在 \(O(n)\) 空间内解决。
首先上来离散化，然后考虑莫队。发现这个东西增加一个数是 \(O(1)\) 的，但删除一个数至少要 \(O(\log n)\) 才能做，所以我们考虑只增。首先询问按照普通莫队的方法排序，然后处理 \(l\) 在一块，而且 \(r\) 递增的询问。设块的右端点为 \(mid\)，则 \((mid,r]\) 可以只添加数来解决，而 \([l,mid]\) 这一段直接暴力（长度 \(\sqrt{n}\)）。总时间复杂度是 \(O(n\sqrt{n})\) 的。
于是像区间众数这种东西也可以用回滚莫队做了。