莫队

莫队算法是由莫涛提出的算法，可以解决一类离线区间询问问题，适用性极为广泛。同时将其加以扩展，便能轻松处理树上路径询问以及支持修改操作。

普通莫队

（以下关于最优性以及复杂度的证明（也就是所有的证明），可到这个大佬的博客里去找）

设定块大小 T，将 m 个询问 [l,r] 离线下来，以 (⌊L/T⌋,R) 为关键字排序后，依次处理每个询问。

根据我的理解，莫队是个优化的暴力

众所周知，莫队是离线的算法。离线，也就是说需要把询问记录下来，然后进行排序，会有一些优化

1s内据说能过n < 2e5的数据，在n比较小，m比较大的时候，比如n < 5e4而m < 1e6，T = sqrt(n)，其他时候还是让T = sqrt（m）吧，这样最优，证明略

排序的时候，奇数块按右端点升序排列，偶数块按右端点降序排列，证明略

===================================================

然后我们来写一下代码

需要用双指针L，R来写，这也是莫队比暴力循环优化的地方，就是有些循环算重的莫队只算了一边

struct stu{
    int l,r;
    int id;
    int block;
    bool operator <(const stu &x) const {
        if(x.block == block)
            if(block % 2) return x.r < r;
            else return x.r > r;
        return x.block < block;
    }
        //莫队的普通排序，这样排更优
}q[N];

这个就是处理读入问题以后的排序方式了

int l = 1;
int r = 0;
for(int i = 1;i <= m;i ++)
    {
        while(l < q[i].l) del(l ++);
        while(l > q[i].l) add(-- l);
        while(r < q[i].r) add(++ r);
        while(r > q[i].r) del(r --);
        ans[q[i].id] = ask();
    }

这个就是核心循环了，有了这些，就可以去做题了

模板题 ：P1494 [国家集训队]小Z的袜子

小Z的袜子题解

模板题2：P2709 小B的询问

带修莫队

（咱也不知道为啥这么叫，也许是“自带修改操作的莫队”）

做莫队的时候发现了另外一种题，就是有操作有询问的题，操作一次需要改一些值才能接着询问

所以

我们增加一维时间轴，即每次询问变成 [l,r,t]。

依然设定块大小 T，然后以 (⌊l/T⌋,⌊r/T⌋,t) 为关键字排序，依次处理每个询问。

（太妙了，所以我就直接把大佬的粘过来了）