莫队学习笔记

\(\text{莫队是一种离线算法。}\)

\(\text{莫队 = 分块 + 暴力}\)

借用的内容
https://blog.csdn.net/u011815404/article/details/88317786
https://www.cnblogs.com/WAMonster/p/10118934.html
https://blog.csdn.net/Enzymii/article/details/77905451
https://blog.csdn.net/wangqianqianya/article/details/89409522
https://www.myblog.link/2016/01/26/MO-s-Algorithm/
https://blog.csdn.net/huayunhualuo/article/details/52153449
https://blog.csdn.net/a1351937368/article/details/78429044
https://blog.csdn.net/qq_38891827/article/details/82190013
https://blog.csdn.net/chenxiaoran666/article/details/81253315
https://blog.csdn.net/chenxiaoran666/article/details/81251960
https://blog.csdn.net/Runner__/article/details/51398047

一般的区间问题都可以使用莫队。
\(\text{莫队的灵魂在于：如果你知道了[L,R]的答案。你可以在O(1)的时间下得到[L,R-1]和[L,R+1]和[L-1,R]和[L+1,R]的答案的话。就可以使用莫队算法。}\)

\(\text{前置芝士：分块 ， sort ， LCA/树剖（树上莫队）}\)

\(\text{莫队就是把所有的询问先存下来 排完序一个个玩}\)

\(\text{大概就是这个样子:如果一段区间是l - r的 那么左指针还是留在l 右指针是留在r的}\)
\(\text{对于下一次操作:莫队会把 上一次左边的位置 移到这一次的位置 右边也一样}\)
\(\text{这样的话 对于朴素暴力已经有了足够的优化 但是还是很慢 最坏情况还是(N*M)的}\)
\(\text{我们考虑排序：把这个按左端点排序 左端点相同时按右端点排序 这样的话是可以证明的优化 因为左端点只会往右}\)
\(\text{对于一种排序我不会证明其复杂度 不过好像真的快很多呢}\)

(转自https://blog.csdn.net/u011815404/article/details/88317786)

int l=1,r=0,ans=0;
for(int i=1;i<=m;i++){
    while(l>q[i].l) add(--l);//[l-1,r]
    while(l<q[i].l) del(l++);//[l+1,r]
    while(r<q[i].r) add(++r);//[l,r+1]
    while(r>q[i].r) del(r--);//[l,r-1]
    res[q[i].id]=ans;//存储答案
}

这是离线莫队的裸的板子（真的就这么短的四句话只是add和del里面要加内容。。）

至于块的大小在这儿

对于复杂度的分析
\(\text{对于左指针：我们考虑最坏情况:莫队的添加删除是O(1)的 那么处理块i的最坏复杂度是$O(x_i \sqrt(n))$}\)
\(\sum_{i = 1}^{n} x_i * \sqrt{n} + n * \sqrt{n}\) = \(O(n\sqrt{n})\)
\(\text{对于右指针：如果我们按照右端点排序 最坏情况显然是O(n)的即从1跳到n}\)
由此可以推出 莫队的复杂度大概就是一个 \(\theta(n \sqrt{n})\)
莫队代码都很短的 只要别把 L++ 写成 ++L

例题整理
https://www.lydsy.com/JudgeOnline/problem.php?id=2038 小Z的袜子
https://www.lydsy.com/JudgeOnline/problem.php?id=4540
https://www.luogu.org/problem/P1494 小Z的袜子(双倍经验)
http://codeforces.com/contest/617/problem/E
https://www.spoj.com/problems/DQUERY/en/
http://codeforces.com/problemset/problem/86/D
http://acm.hdu.edu.cn/showproblem.php?pid=5213
http://acm.hdu.edu.cn/showproblem.php?pid=5381
http://acm.fzu.edu.cn/problem.php?pid=2226
http://acm.hdu.edu.cn/showproblem.php?pid=4638
http://acm.hdu.edu.cn/showproblem.php?pid=4676
带修改的莫队
https://www.luogu.org/problem/P1903
离散化
https://www.lydsy.com/JudgeOnline/problem.php?id=3289
树上莫队
https://www.lydsy.com/JudgeOnline/problem.php?id=1086

bzoj4866
bzoj3809 还有在衢州欠下的题（小声

莫队的板子：https://blog.csdn.net/wangqianqianya/article/details/89409522
例题先鸽 明天再更

莫队学习笔记

原文：https://www.cnblogs.com/qf-breeze/p/11380502.html