普通莫队
把询问离线下来，按左端点分块，同一个块内按右端点排序。
块长 \(b=\dfrac{n}{\sqrt m}\)，注意特判 \(m=0\) 或让 \(b=0\) 的 sb 出题人，会 RE。
记录两个指针 \(l,r\)，依次挪动到待查询区间。注意要先扩大再缩小，否则会出现正确性上的问题。
trick：奇偶排序
可以按照块序号的奇偶决定 \(r\) 的递增或递减。
感性理解：就是 \(r\) 在第一块从 \(1\) 跑到 \(n\)，本来在第二块要回到前面再走一遍，结果第二块逆序排序，就在回来的路上解决了所有第二块的询问。
P2709 小B的询问
从 \(c\) 到 \(c+1\) 会产生 \(2\times c+1\) 的贡献。
从 \(c\) 到 \(c-1\) 会产生 \(2\times c-1\) 的负贡献。
记录一个桶和一个 \(sum\)，硬算。
SP3267
区间数颜色个数，开个桶，摁做。
CF617E / P4462
询问区间内有多少个子区间的异或和为 \(k\)。
依然是数颜色，开个桶。
假如 \(a \oplus x=k\) 其中 \(a\) 已知，那 \(x=k \oplus a\)，于是新加入一个 \(a\) 的贡献为 \(cnt_{k\oplus a}\)。
P3709
转换一下题意可得每次选无序上升子序列最优。
无序上升子序列：就是随便找一组上升的数，不考虑顺序。
也就是区间询问最少能被几个无序上升子序列覆盖。
考虑到每个数在一组无序上升子序列中只能被选到一次。
也就是求区间众数的大小。发现加很好做，但删除不太容易，于是就有了回滚莫队做法。
也可以记录一个桶的桶 \(ccnt\)，就是记录出现次数的出现次数，外加一个指针记录当前最大的 \(ccnt\)。加入时让 \(ccnt_{k+1}+1,ccnt_{k}-1\) ，减掉时 \(ccnt_{k}-1,ccnt_{k-1}+1\)。
发现数字可能很大，但数字的种类不多，离散化即可。
P4867
数颜色种类，但是种类要求在一个值域范围内。
用值域分块即可。
带修莫队
直接上例题。
P1903
数区间颜色种类，带修。
用结构体存一下每个修改。
我们在原先排序的基础上，对于所有 右端点 在同一个块中的查询按 \(t\) 升序排序。
记录三个指针 \(l,r,t\)，分别指向当前区间的左右端点、修改时间轴上的时间，每个查询先移动端点，再处理修改，在当前区间内的修改才需要统计贡献。
块长设到 \(O(n^{\frac{2}{3}})\)。
work 要传两个参数，询问和修改的编号，询问的编号仅用于查询是否与当前答案有关。
swap 的操作很巧妙，因为回溯的时候会把这个数交换回来，而其他修改与之无关。
CF940F
不会。
树上莫队
用于处理树上的区间查询。
而莫队只能在序列上用，建出这棵树的括号序并处理出 lca，按普通莫队去跑，分类讨论子树关系，然后特判 lca 的情况。
修改时注意不一定是加点或者删点，而要根据这个点的出现次数判断是加点还是删点。
规定第一次出现是 \(dfn\)，第二次出现为 \(low\)。
SP10707 COT2 - Count on a tree II
树上的区间数颜色，树上莫队板子。
跑出括号序，有祖孙关系就存区间 \([dfn_x,dfn_y]\)，没有祖孙关系就存 \([low_x,dfn_y]\)，外加一个 \(lca\)（先要保证 \(dfn_x<dfn_y\)）。
记录一个 bool 的 \(use[]\)，访问过一回就删掉，否则就加上。
回滚莫队（只增加/只减少莫队）
步骤
-
按普通莫队排序（不可以奇偶块优化）
-
记录每个块的左右端点 \(L_i,R_i\)
-
对于每个询问
-
若左右端点在同一个块内：暴力
-
否则
- 之后会有一段询问 \(q[j].r>R_i\)
- 将当前端点移动到 \(l=R_i+1,r=R_i\) 的位置
- 先移动右端点到目标位置（询问的 \(r\) 单调递增）
- 移动左端点到目标位置
- 记录答案
- 恢复左端点到 \(l=R_i+1\)
-
AT_joisc2014_c 歴史の研究
回滚莫队模板。
只有左右端点移动到指定位置的尾部时才能用 memset，因为只有根号次移动。
清空暴力的 cnt 数组和回滚的时候都不能 memset，这两个操作都会被卡到 \(O(n^2)\)。