证明:
当我们第i个询问转移的第i+1个询问时
如果第i个询问区间和第i+1个询问区间的左端点所在块的编号相同,那么左端点的移动不会超过\sqrt{n}。
也就是说,左端点一直在块内移动的总复杂度为O(n*\sqrt{n})(因为左端点最多转移n次,减去左端点跨越块的部分,不足n
同时由于右端点升序,那么若l,l+1,,,r-1,r的询问区间左端点所在块的编号相等,那么右端点的移动不会超过n次。有一位有\sqrt{n}个块,
所以这一部分的复杂度是O(n*\sqrt{n})的。
考虑左端点跨越块的情况,每次跨越最大是O(2*\sqrt{n})那么左端点跨越块的复杂度O(n*\sqrt{n})的。
又在这个期间,每次左端点跨越的时候,右端点可能要移动O(n)次,一共左端点跨越\sqrt{n}个块,所以右端点复杂度是O(n*\sqrt{n})的。
综上莫队算法的排序保证时间复杂度是O(n*\sqrt{n})的
以下内容借鉴自洛谷题解
原版莫队是将区间(l,r)视为点(l,r),带修改的即加一维时间轴(l,r,t)
对于t轴的移动可以保存每次修改,如果修改在(l,r)间则更新
分块方法可以参照原版莫队,先将l分块,再讲r分块,同一块的按t排序
块大小为\sqrt [3] {nt}可以达到最快的理论复杂度O\left( \sqrt [3] {n^{4}t}\right),证明如下
设分块大小为a,莫队算法时间复杂度主要为t轴移动,同r块l,r移动,l块间的r移动三部分
t轴移动的复杂度为O\left( \dfrac {n^{2}t}{a^{2}}\right),同r块l,r移动复杂度为0\left( na\right),l块间的r移动复杂度为0\left( \dfrac {n}{a}\right)
三个函数max的最小值当a为\sqrt [3] {nt}取得,为O\left( \sqrt [3] {n^{4}t}\right)