为了方便以下设 $n$ 为网格的宽度，$(i,j)$ 表示第 $i$ 行第 $j$ 列的点，其中 $i\in\{0,1,2\},1\le j\le n$。对于一条 $(a,b)$ 到 $(c,d)$ 的路径，若 $b\ne d$，则无论它怎么复杂，$\forall f\in[b,d-1]$，必然有一段形如离开第 $f$ 列的某个点、进入 $f+1$ 列同一行的点，假设这两个点都在第 $e$ 行，那么 $(a,b)$ 到 $(c,d)$ 的路径就能被拆成 $(a,b)$ 到 $(e,f)$、$(e,f+1)$ 到 $(c,d)$ 两段。于是可以考虑不断选定这样的分界线，统计某个范围内跨过该分界线的点对的最短路之和。显然可以考虑分治。

设当前分治区间 $[l,r]\subseteq [1,n]$，当 $l=r$ 时需要计算第 $l$ 列 $3$ 个点之间的最短路。由于本题中路径长度等于路径中点权和，而点权和都非负，于是对于相邻的点直接走一步就是最优的。而对于 $(0,l)$ 和 $(2,l)$，类似可以发现它们的最短路一定形如：从 $(0,l)$ 出发，往一个方向走一段距离，然后往下走两步到达第 $2$ 行，再往反方向走到 $(2,l)$。这个路径很容易拆成前缀和相减的形式，分成最开始向左走、向右走两种情况，预处理一个前后缀 $\max$ 即可。

取 $mid=\lfloor(l+r)/2\rfloor$，本轮统计第 $l\sim mid$ 列到第 $mid+1\sim r$ 列的点的答案，此时需要 $l\sim mid$ 中的点到 $(0,mid),(1,mid),(2,mid)$ 的最短路、$mid+1\sim r$ 中的点到 $(0,mid+1),(1,mid+1),(2,mid+1)$。注意到这相当于计算每个分治区间中的点到区间边界上的两列点的最短路，而这可以继承子区间答案 + 枚举中转点解决。设 $g(x,y,o)$ 表示 $(x,y)$ 到 $(o,mid)$ 的最短路，$f(x,y,o)$ 表示 $(x,y)$ 到 $(o,mid+1)$，那么我们要计算： $$ \sum_{x\in\{0,1,2\},l\le y\le mid}\sum_{z\in\{0,1,2\},mid+1,\le w\le r}\min_{k\in\{0,1,2\}}g(x,y,k)+f(z,w,k) $$ 为了能把贡献拆成左右两边，考虑先枚举最后一个 $\min$ 取到的 $k$（当值相同时需要钦定一个优先级，这里假设优先取较小的 $k$），那么答案就表示成 $$ \sum_{k\in\{0,1,2\}}\sum_{(x,y)}\sum_{(z,w)}\left[ k'\ne k,g(x,y,k')+f(z,w,k')\ge g(x,y,k)+f(z,w,k)+[k＜k']\right](g(x,y,k)+f(z,w,k)) $$ 以 $k=1$ 为例，此时有贡献的 $((x,y),(z,w))$ 要满足：

• $g(x,y,0)+f(z,w,0)\ge g(x,y,1)+f(z,w,1)+1$ 即 $g(x,y,0)-g(x,y,1)\ge f(z,w,1)-f(z,w,0)+1$；
• 类似可得 $g(x,y,2)-g(x,y,1)\ge f(z,w,1)-f(z,w,2)$。

这是个二维数点形式，把左边点当修改点、右边点当查询点，对于 $k=0,1,2$ 都做一遍二维数点即可。时间复杂度 $O(n\log^2n)$。