几何理解

理解

概念映射

	原始概念	映射概念
状态空间	序列的所有区间	$(l, r)$ 平面，定义域为 $[1,n]\times [1,n]$ 的整数格点
状态函数	区间 $(l, r)$ 内的统计量	二元离散函数 $f(l, r)$
目标点集	所有询问	点集 $Q=\{(l_i, r_i)\}$
计算量	时间复杂度	点集路径曼哈顿距离
移动算子	移动函数	$f$ 的偏导
	include(--l)	$\Delta_{l^-}$
	include(++r)	$\Delta_{r^+}$
	exclude(l++)	$\Delta_{l^+}$
	exclude(r--)	$\Delta_{r^-}$

离散线积分

• 将点集 $Q$ 串接成一条有向路径
• 沿路径对 $\Delta$ 做线积分
• 到达某点 $Q_i$ 时，$\Delta$ 的线积分值即为 $f(Q_i)$

减少投影

路线投影到 $l$ 轴或 $r$ 轴后，重叠部分为重复计算，应尽量减少

• 分块：约束 $l$ 方向抖动范围到 $\sqrt{n}$
• 排序：使 $r$ 方向块内单调上升
• 奇偶优化：蛇形路线 $r$ 跨块时减少重复计算

旅行商问题（TSP）

上述理解下，莫队算法相当于旅行商问题，遍历 $Q$ 中的所有点，路径代价为曼哈顿距离。

普通莫队

暴力求解

一团乱麻，在平面上乱飞

普通莫队

块内 $Z$ 字形走位，块间转移时有无效路径

奇偶排序

基本不走回头路

带修莫队

普通带修

奇偶排序