莫队算法/分块思想
引入
对于区间问题，常常会使用线段树维护，但是对于一些数据合并复杂度无法 \(O(1)\) 解决。所以不能使用，应当使用莫队算法。
定义
对于离线处理的查询问题，通过合理安排这些计算的次序，得到一个较优的复杂度
例题1
一个长度为 \(n\) 的序列，询问 \(m\) 次 \([L,R]\) 的区间内至少重复三次的数有多少。
应当暴力，拓展L，R边界。以查询左端点所在块为第一关键字、右端点大小为第二关键字，从小到大排序。
拓展莫队
- 带修莫队
问题加入修改
记录指令修改前后的值，记录查询时做过几次修改，对询问排序的优先级改为：第一关键字 L 所在块，第二关键字 R 所在块，第三关键字，做了几次修改。
然后暴力，带上更改到对应修改时间的操作。
- 回滚莫队
操作加入容易，删除难
询问排序相同，枚举左端点所在的块的所有询问。
左右端点在同一块的暴力统计，否则记录一个块尾到当前右端点的区间，每次暴力回滚添加元素，然后回溯还原。
- 树上莫队
问题在树上
将树变成一个序列，然后莫队处理。
实现
有些东西是做出来的，不是学出来的。
略
标签：修改,分块,关键字,算法,端点,莫队 From： https://www.cnblogs.com/life-of-a-libertine/p/17993203