莫队

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

具体做法

先上一道例题。

[

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

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

代码就是：

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

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

具体跳的代码：

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

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

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

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

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

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

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

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

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

具体代码可以看

带修改的莫队

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

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

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

代码就是：

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

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

复杂度证明

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

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

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

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

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

树上莫队

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