莫队二次离线 学习笔记

## 莫队二次离线用来做什么 用于优化莫队。 有些时候，莫队区间首尾端点的更新并不是 $\Theta(1)$ 的。 设该复杂度为 $\Theta(k)$，则总复杂度变为 $\Theta(n\sqrt{n}\cdot k)$，不可接受。 这时便需要二次离线进行优化。 ## 主要思想 ### 转化 设 $f([l,r],x)$ 为 $x$ 在 $[l,r]$ 中对答案的贡献。 则每将 $[l,r]$ 扩大至 $[l,r^\prime]$ 的范围，新增的贡献为： $$\sum\limits_{x=r}^{ r^\prime -1} f([l,x],x+1)$$ 注意到 $f([l,x],x+1)=f([1,x],x+1)-f([1,l-1],x+1)$ 则原式等于： $$\sum\limits_{x=r}^{ r^\prime -1} f([1,x],x+1)-\sum\limits_{x=r}^{ r^\prime -1} f([1,l-1],x+1)$$ ### 分别处理 上式中，**前一个和式**的值仅与 $x$ 有关，共 $n$ 种情况。 每次 $\Theta(k)$ 地加入一个点，即可 $\Theta(nk)$ 预处理。 **后一个和式**的话，由于莫队的性质，有： - 所有 $[r,r^\prime-1]$ 的**总长度**是不大于 $\Theta(n\sqrt{n})$ 的。 - 所有 $[r,r^\prime-1]$ 的**总个数**是不大于 $\Theta(n)$ 的。 注意到每次询问的贡献区间是不变的，都是 $[1,l-1]$。 所以把每个 $[r,r^\prime-1]$ 记录在 $l-1$ 的位置，这样空间复杂度是 $\Theta(n)$ 的。 但是怎么计算呢？ ### 再次转化 回想我们暴力 $\Theta(n\sqrt{n}\cdot k)$ 的过程，相当于对于每个 $l-1$ 的位置，$\Theta(k)$ 地计算 $[r,r^\prime-1]$ 中所有的值的贡献。 注意到所有 $l-1$ 的个数是 $\Theta(n)$ 的，而所有 $[r,r^\prime-1]$ 的个数是 $\Theta(n\sqrt{n})$ 的。 因此复杂度是 $\Theta(n+n\sqrt{n}\cdot k)$ 的。 怎么优化？ 自然是把 $k$ 移过去，即： $$\Theta(n+n\sqrt{n}\cdot {\color{red}k})\ \Rightarrow\ \Theta(n\cdot{\color{red}k}+n\sqrt{n})$$ 换言之，即不采用 $\Theta(1)$ 地扩大 $[1,l-1]$ 的范围，$\Theta(k)$ 地计算所有 $[r,r^\prime-1]$ 的贡献。 而是 $\Theta(k)$ 地在扩大 $[1,l-1]$ 的范围时反着预处理答案，$\Theta(1)$ 计算贡献。 其余三种移动同理，如 $[l,r]$ 扩大至 $[l^\prime,r]$ 即为： $$\sum\limits_{x=l^\prime}^{l-1} f([x+1,r],x)$$ $$=\sum\limits_{x=l^\prime}^{l-1} f([1,r],x)-\sum\limits_{x=l^\prime}^{l-1} f([1,x],x)$$ **时间复杂度 $\Theta(nk+n\sqrt{n})$，空间复杂度 $\Theta(n)$。** ## 例题 ~~正在写~~ - [P4887 【模板】莫队二次离线（第十四分块(前体)）](https://www.luogu.com.cn/problem/P4887) - [P5047 [Ynoi2019 模拟赛] Yuno loves sqrt technology II](https://www.luogu.com.cn/problem/P5047)