莫队

莫队是一种离线算法，其思想本质是改变询问的顺序，然后利用上一次询问的结果以降低复杂度。

具体做法

先上一道例题。

[2009国家集训队]小Z的袜子

先对位置分块，设块的大小为(sz)。

那么我们对询问以左端点所在的块为第一关键字，右端点为第二关键字进行排序。

代码就是：

int cmp(data A,data B) {return bel[A.l]==bel[B.l]?A.r<B.r:A.l<B.l;}

然后对于一个询问转换到另外一个询问，直接暴力跳就好了。

具体跳的代码：

while(ql<a[i].l) del(ql++);
while(ql>a[i].l) add(--ql);
while(qr<a[i].r) add(++qr);
while(qr>a[i].r) del(qr--);

其中(add)和(del)都是(O(1))的。

那么我们来分析下复杂度：

对于排序后相邻两个询问，一定为下面两种情况之一：

左端点在一个块上，那么，左端点此时是无序的，每次最多跳的复杂度为(O(sz))，这部分共(O(ncdot sz))。

此时，右端点是有序的，对于每一个块的花费最多是(O(n))，这部分共(O(n^2/sz))。

左端点不在一个块上，这种情况最多只有(O(n/sz))次，左端点花费共(O(n))，右端点一次最多是(O(n))，共(O(n^2/sz))。

综上，复杂度为(O(n^2/sz+ncdot sz))。

此时，(sz=sqrt{n})时，复杂度最优，为(O(nsqrt{n}))。

具体代码可以看这里

带修改的莫队

同样，先分块，设块的大小为(sz)。

这里，我们需要对时间戳搞事情。

排序改成了，左右节点的块为第一第二关键字，时间戳为第三关键字。

代码就是：

int cmp(data a,data b) {return bel[a.l]==bel[b.l]?(bel[a.r]==bel[b.r]?a.t<b.t:bel[a.r]<bel[b.r]):bel[a.l]<bel[b.l];}

那么，跳的时候也差不多，直接暴力就好了，跳时间戳的时候改一改什么的，这个依题而定。

复杂度证明

那么现在就有了三种情况：

左右端点都在同一个块，这样每个块时间戳都可以跳满，左右端点一共有(O((n/sz)^2))种组合，复杂度(O(ncdot (n/sz)^2+ncdot sz))。
左端点在同一个块，右端点不在，这样的话，对于每次，右端点可以跳(O(n))，时间戳也是(O(n))，共计(O(n^2/sz))。
左端点不在同一个块，右端点和时间戳无序，(O(n))跳，共(O(ncdot (n/sz)))。

综上，复杂度是(O(n^ 3/sz^2+ncdot sz))。

那么，最小化的话，即(n^3/sz ^2=ncdot sz)，即(sz=n^frac{2}{3})。

总复杂度(O(n^frac{3}{5}))。

树上莫队

这个我直接是在欧拉序上分块，那么和第一种是一样的，树上莫队和待修莫队模板：[WC2013]糖果公园