莫队二次离线，是由数据结构题之神lxl所发明的一种数据结构。因为莫队中 \(ans\) 的变化同样不要求立刻反应，所以我们可以离线求解莫队中每次 \(ans\) 修改值 \(F(x,[l,r])\)。设单次求解修改值的时间复杂度为 \(O(k)\)，那么莫队二次离线可以将时间复杂度从 \(O(nk\sqrt n)\) 变为 \(O(n\sqrt n+nk)\)。
注：上文、下文的 \(F(x,[l,r])\) 表示区间 \([l,r]\) 对 \(ans_x\) 的贡献，\(f(x,a)=F(x,[1,a])\)。
莫队二次离线的一些限制
莫队二次离线有以下几种限制：
- 当前答案不会影响下一次修改的决策（我就没见过这种情况，有见过的大佬讨论区发一下，谢谢）。
- 满足 \(F(x,[l,r])=f(x,r)-f(x,l-1)\)。
当然，假如 \(O(k)=O(1)\) 的话，你也没有必要进行莫队二次离线。
莫队二次离线（空间 \(O(n\sqrt n)\)）
我们先考虑右指针右移的情况。
设当前右指针为 \(r\)，左指针为 \(l\)，那么一次右指针右移操作对 \(ans\) 的贡献即为 \(F_{r+1,[l,r]}\)，同时 \(r\to r+1\)。
根据限制 2，我们可以将贡献差分为 \(f_{r+1,r}-f_{r+1,l-1}\)。
同理，右端点左移的贡献就是 \(f_{r,l-1}-f_{r,r-1}\)，左端点右移的贡献就是 \(f_{l,l}-f_{l,r}\)，左端点左移的贡献就是 \(f_{l-1,r}-f_{l-1,l-1}\)。
我们在移动端点的同时，记录这些需要求的贡献，然后在遍历序列的同时进行求解即可。
例如模板题 luogu4887，普通莫队的时间复杂度为 \(O(\binom{14}kn+n\sqrt n)\)，空间复杂度平颈为记录所有贡献，为 \(O(n\sqrt n)\)。这样并不能通过此题，因为时间常数和空间过大了。但还是附上代码：
[code]#include#define ll long longusing namespace std;const int N=1e5+5,M=(1m>>k,dfs(0,0,0); //这个马上讲 for(int i=1;i>a,nw1=tg[a]; for(int j=1;jqu.l>>qu.r,qu.id=i; memset(tg,0,sizeof(tg)); sort(qu+1,qu+m+1,cmp); for(int i=1,l=1,r=0;iqu.r){ ans[qu.id]-=nw1[r]; qe[l-1].push_back({r--,qu.id,1}); }while(l |
提升卡
置顶卡
沉默卡
喧嚣卡
变色卡
千斤顶
照妖镜
