§ 0x01 前言

女装灰太狼 2018 整出来的黑科技。

§ 0x02 大体思想

普通的莫队一般有 $\Theta(n\sqrt{n})$ 次的区间移动。

那么就分别有 $\Theta(n\sqrt{n})$ 次的修改与查询。

莫队二次离线就是把 $\Theta(n\sqrt{n})$ 次的修改与查询优化到了 $\Theta(n)$ 次的修改，$\Theta(n\sqrt{n})$ 次的查询。

从而使得我们可以使用 $\Theta(\sqrt{n})$ 的修改，$\Theta(1)$ 的查询来优化复杂度。

§ 0x03 具体做法

二次离线的使用需要题目的答案满足区间可减性，比如说区间点对数。

为方便理解，我们定义一个四元函数 $F(l_{1},r_{1},l_{2},r_{2}),l_{1}\le r_{1},l_{2}\le r_{2},l_{2}\ge r_{1}$ 为区间 $[l_{1},r_{1}]$ 以及区间 $[l_{2},r_{2}]$ 的两个区间中的点对数量，区间内部不算。

换句话说，就是

$$F(l_{1},r_{1},l_{2},r_{2})=\sum_{i=l_{1}}^{r_{1}}\sum_{j=l_{2}}^{r_{2}}\mathrm{K}(a_{i},a_{j})$$

其中 $a$ 代表原序列，$\mathrm{K}(m,n)$ 表示 $m,n$ 两个点是否满足点对的要求，满足的话 $\mathrm{K}(m,n)$ 为 1，否则为 0。

比如逆序对就是 $K(m,n)=[m\ge n]$。

我们设我们莫队当前的区间为 $[l,r]$，我们要扩展 $[l,r]$ 到 $[l,r'],r'>r$。

我们设当前区间的贡献为 $\mathrm{cont}(l,r)$。

那么

$$\begin{aligned} &\mathrm{cont}(l,r') \\ &=\mathrm{cont}(l,r)+\sum_{i=r+1}^{r'}F(l,i-1,i,i) \\ &=\mathrm{cont}(l,r)+\sum_{i=r+1}^{r'}(F(1,i-1,i,i)-F(1,l-1,i,i)) \\ &=\mathrm{cont}(l,r)+(\sum_{i=r+1}^{r'}F(1,i-1,i,i))-F(1,l-1,r+1,r') \end{aligned}$$

观察到

$$\sum_{i=r+1}^{r'}F(1,i-1,i,i)$$

这一部分可以用前缀和搞定。

这个东西讲成汉字就是区间 $[1,i-1]$ 中大于等于 $a_{i}$ 的数量的和。

那么对于每一个 $i$ 我们都可以用树状数组预处理出来。

我们主要来看

$$F(1,l-1,r+1,r')$$

这一部分。