优雅的暴力——莫队算法学习笔记（超详细）

一、问题引入

当有一道题每次问你一个区间的某某东西，而这个东西不可合并（不可线段树）不可差分（不可树状数组）分块后不好合并/无法合并（不可分块），但是支持离线并且任意一个区间能通过扩张和收缩得到其它区间的答案，那么这道题就可以莫队。
二、什么是莫队

首先，如果有一道区间可扩张收缩的题（不需要支持离线），你是不是可以先求出第一个区间的答案，然后通过左右端点的扩张和收缩求出其它区间的答案，但是你会发现最坏时间复杂度跟暴力的 \(O(qn)\) 一样，但是这个时候神奇的事情就来了，我们给它将询问离线一下，然后通过一种神奇的排序之后，它的时间复杂度就变成了 \(O((q+n) \sqrt n)\) 了！这个神奇的排序是什么呢，就是先将 \(1\) 到 \(n\) 的所有点分个块，然后排序时先按照 \(l\) 所在的块从小到大排序，如果有两个 \(l\) 相等，再按照 \(r\) 的从小到大排序。
三、如何证明莫队时间复杂度

首先你会发现左指针单次移动如果是在同一个块，那么单次移动时间复杂度为 \(O(\sqrt n)\)，因为一个块的大小最多为 \(\sqrt n\)，而左指针又不能移出这个块，然后如果是不同一个块的移动，因为每次最多移动 \(O(\sqrt n)\) 步，所以单次移动时间复杂度为 \(O(\sqrt n)\)，然后开始考虑总移动，你就会发现时间复杂度为 \(O(q \sqrt n+n)\)，\(O(q\sqrt n)\) 是同一个块内移动的总复杂度（因为要移动 \(q\) 次嘛，所以就是 \(O(q \times \sqrt n) = O(q \sqrt n)\)），然后 \(O(n)\) 指的是不同一个块的移动的总时间复杂度，因为发生这种情况只会有 \(O(\sqrt n)\) 次，所以总时间复杂度为 \(O(\sqrt n \times \sqrt n) = O(n)\)，然后考虑右指针移动，你会发现根据莫队的排序右指针块内单调递增，但是跨越块就不一定掉递增，那么你会发现跨越块的行为最多只会出现 \(O(\sqrt n)\) 次，而每次最坏移动 \(O(n)\) 步，所以总时间复杂度为 \(O(\sqrt n \times n+n) = O(n \sqrt n+n) = O(n \sqrt n)\)，所以最后时间复杂度为 \(O((n+q) \sqrt n)\)，当然，在计算过程中，我们省掉了好几个常数，所以莫队的常数也是有点大的。
四、莫队板子

[code]#includeusing namespace std;const int N = 5e4+5;//可自由变动struct node{        int l;        int r;        int id;}b[N];int a[N];int len;int cmp(node x,node y){        int idx = (x.l-1)/len+1,idy = (y.l-1)/len+1;        return idx == idy?x.r