通过SPOJ 10707 COT2-Count on a tree II这道题目来学习一下 树上莫队
当需要离线查询 树上 的多区间问题时,可以使用 树上莫队 来解决

主要通过 欧拉序 将树转化为一条链,然后在链上执行普通莫队的操作

通过AtCoder 1219 歴史の研究这道题目来学习一下 回滚莫队
回滚莫队 适用于容易进行add操作,而不容易实现del的情况

通过莫队的分块,指针移动的思想,可以让左指针进行回滚操作, 近似 达到del的效果

通过Luogu P1903 数颜色/维护序列这道题目来学习一下 带修莫队
顾名思义,带修莫队 不仅要支持普通莫队的查询操作,还要支持数据中途的修改

比如这道题目,需要实现以下目标

1. 查询$[L,R]$区间内不同颜色画笔的种数
2. 将$pos$处的画笔替换为$color$颜色

达到这个目标,可以在普通莫队的基础上加一个时间维度,实现 带修莫队

这篇文章来记录一下莫队算法时间复杂度的简单(不严谨)计算

首先分析一下莫队算法的时间复杂度有哪些方面构成

1. 对询问Query数组的排序
2. 区间左指针的移动
3. 区间右指针的移动

题目传送门: 「Luogu P1494」小Z的袜子
一道推公式，后使用莫队 玄学 优化的题目