网格图有一个优美的性质，它的最小割的大小等于较短边的长度，不超过 $\sqrt S$，其中 $S$ 为网格图面积。

所以网格图上的最短路可以分治地做，网格上一块矩形区域，在较长边中点处切开。此时两个点间的最短路分为，只经过其中一部分的和跨过切面的。只经过其中一部分的，分治处理；跨过切面的，我们以切面上每个点为源，在整个区域内求最短路。对于一块面积为 $S$ 的矩形区域，所需时间为

$$\displaylines{T(S)=2T\left(\frac S2\right)+\sqrt S\cdot S\log S }$$

根据主定理有 $T(S)=O(S^\frac32\log S)$。

物品成序列，每次对其中的一个区间做背包问题。

设一组物品 $S$ 限定体积不超过 $m$ 的情况下能够取得的最大价值为 $f_S(m)$。如果使用线段树维护区间内元素的 $f_S$ 值会带来大量复杂度为 $O(m^2)$ 合并。而插入单个元素时间复杂度为 $O(m)$，所以我们倾向于使用更多的插入操作而非合并操作。

考虑对区间进行分治，将每个询问放到最小的完全包含询问区间的分治区间进行处理。显然询问区间一定跨过该分治区间中点。于是对于每个分治区间，预处理其前半部分的每个后缀的 $f$、后半部分的每个前缀的 $f$，各 $O(nm)$ 的时间复杂度，然后对所有跨过区间中点的询问，进行一次 $O(m)$ 的合并（因为这里只需要算出 $f$ 的一处点值）即可求得答案。

复杂度为 $O(nm\log n+mq)$