莫队

发布时间 2023-11-12 12:59:52作者: mRXxy0o0

基本形态

处理可离线的区间问题,将询问按左块号+右端点排序,快速地转移到相邻区间。

复杂度要求

\(O(1)\) 添加(可以回滚+可撤销数据结构,避免删除时计算答案),\(O(\sqrt n)\) 以下查询(套分块 \(\dots\))。

技巧

大多数莫队维护的是区间答案,但也可以指代 \([1,l]\)\([1,r]\) 两部分的答案。只要可以快速转移,都是可以的(再套一个回滚??)

比如这道的四个 while 就有一定区别,还涉及了前缀与差分的思想。并且由于区间表示的特殊性,这里允许 \(l>r\)


对于一部分题目,有严格要求 \(l\le r\),可以通过先加后删做到。


树上的莫队可以通过括号序转化成序列问题,出现两次的点没有贡献。


对于带修莫队,则要注意时间对区间答案的先后影响,比如这道带修树上括号序莫队(一看就很毒瘤)需要时刻注意改 \(time\) 时对区间的影响

写着写着突然想出一道缩点+带修树上莫队题的想法((

据说还有一些更ex的莫队,但是不会(摊手)