🕶 很酷不证明。

普通莫队

离线查询序列。按左端点所在块为第一键值，右端点为第二键值，排序，暴力移动端点。 $\mathcal{O}(n^{\frac{3}{2}})$ 。

带修莫队

离线查询序列。按左端点所在块为第一键值，右端点所在块为第二键值，时间戳为第三键值，排序，暴力移动端点。块长 $n^{\frac 23}$ 。 $\mathcal{O}(n^{\frac{5}{3}})$ 。

回滚莫队

只插入不删除或只删除不插入。咕着先。