高维莫队

我们可以将莫队算法从一维扩展到更高维度。

考虑正在维护 $k$ 维结构的信息，且每一维的大小分别为 $n_1,n_2,\cdots,n_k$。为了下文叙述方便，我们将维度大小序列复制一份，得到 $n_{k+1},\cdots,n_{2k}\quad(n_i=n_{i-k})$。我们同时维护 $2k$ 个指针，第 $i\ \ (i\leq k)$ 个指针维护第 $i$ 维左端点，第 $i\ \ (k<i\leq 2k)$ 个指针维护第 $i-k$ 维右端点。按询问处理顺序依次移动到每个询问对应的位置上。

现在考虑对询问分块、排序。记对于前 $2k-1$ 个指针，分块大小分别为 $s_1, s_2,\cdots,s_{2k-1}$。记一共有 $q$ 个询问。我们按照第 $i\ \ (i<2k)$ 个指针所属小块的编号作为第 $i$ 关键字，第 $2k$ 个指针位置作为第 $2k$ 关键字对询问排序。于是总移动次数为 $$\newcommand\bigO[1]{\operatorname{O}\left(#1\right)}\bigO{q\sum_{i=1}^{2k-1}s_i}+\sum_{i=1}^{2k}\bigO{\frac{\prod_{j=1}^{i}n_j}{\prod_{j=1}^{i-1}s_j}}\quad\text{（块内移动、本维指针因更优先关键字重置）}$$

上式右侧一项中，显然只有 $\bigO{\frac{\prod_{j=1}^{2k}n_j}{\prod_{j=1}^{2k-1}s_j}}$ 最显著。于是得到总移动次数为 $$\bigO{q(s_1+s_2+\cdots+s_{2k-1})+\frac{n_1n_2\cdots n_{2k}}{s_1s_2\cdots s_{2k-1}}}$$

我们小学二年级就学过“（两实数）和定差小积大”。事实上，我们可以用调整法轻松证明这对于任意整数 $l\ \ (l>1)$ 都成立：$l$ 个实数 $a_1,\cdots,a_l$ 之和为定值 $m$，则当 $a_1=a_2=\cdots=a_l=\frac{m}{l}$ 时有 $\prod_{i=1}^la_i$ 最大，是为 $\frac{m^l}{l^l}$。

于是考虑 $m=\sum_{i=1}^{2k-1}s_i$。令 $N=\prod_{i=1}^{2k}n_i$。我们自然希望 $m$ 固定时有 $\prod_{i=1}^{2k-1}s_i$ 最大以令 $\frac{N}{s_1s_2\cdots s_{2k-1}}$ 最小。所以上式转写为 $$\bigO{qm+\frac{N(2k-1)^{2k-1}}{m^{2k-1}}}$$

我们设 $f(m)=qm+\frac{N(2k-1)^{2k-1}}{m^{2k-1}}$，则 $f'(m)=q-\frac{N(2k-1)^{2k-1}}{m^2k}$。注意到 $f'(m)$ 单增且存在零点，故我们找到其零点并以此计算 $s_i$ 的取值，就能获得最优理论复杂度。实际上为了简便计算，由于 $k$ 通常较小，我们常忽略一些乘积项；故取 $$\begin{aligned} &s_i=\frac{m}{2k}=\sqrt[2k]{\frac{N}{q}}\\ \Longrightarrow&\bigO{kN^{\frac{1}{2k}}q^{\frac{2k-1}{2k}}+q^{\frac{1}{2k}}N^{\frac{2k-1}{2k}}} \end{aligned}$$

注意上式是指针移动次数而非最终复杂度。实际应用中，我们还可以适当将块长减小，届时还请就题分析。