Debug

复杂度证明

普通莫队时间复杂度为O\left( n\times \sqrt {n}\right)

证明：

当我们第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)