🕶 很酷不证明。
普通莫队
离线查询序列。按左端点所在块为第一键值，右端点为第二键值，排序，暴力移动端点。 $\mathcal{O}(n^{\frac{3}{2}})$ 。
带修莫队
离线查询序列。按左端点所在块为第一键值，右端点所在块为第二键值，时间戳为第三键值，排序，暴力移动端点。块长 $n^{\frac 23}$ 。 $\mathcal{O}(n^{\frac{5}{3}})$ 。
回滚莫队
只插入不删除或只删除不插入。咕着先。
EOF
🕶 很酷不证明。
离线查询序列。按左端点所在块为第一键值，右端点为第二键值，排序，暴力移动端点。 $\mathcal{O}(n^{\frac{3}{2}})$ 。
离线查询序列。按左端点所在块为第一键值，右端点所在块为第二键值，时间戳为第三键值，排序，暴力移动端点。块长 $n^{\frac 23}$ 。 $\mathcal{O}(n^{\frac{5}{3}})$ 。
只插入不删除或只删除不插入。咕着先。
可以用@mike来提到mike这个用户，mike会被高亮显示。如果你真的想打“@”这个字符，请用“@@”。