ABC429F

考虑矩形只有三行的性质该怎么利用。

发现我们最终的轨迹中，一定是从左向右；因此可以合并每一列，只需要计算 $i\rightarrow i+1$ 中每行转移的最小值即可。

这样的话，每次修改 $(x,y)$ 时，我们实际上只需要考虑修改 $x-1\rightarrow x$ 和 $x\rightarrow x+1$ 的信息。

可以在每列维护一个长和宽均为 $3$ 的矩阵 $a$：$a_{i,j}$ 代表从当前列的第 $i$ 行到第 $j$ 列的最小距离。这个是容易维护的。

对于列与列之间的转移，我们可以类似于矩阵乘法地进行转移，即枚举两列各从某个位置走到一个相同的位置，于是可以快速求出从 $(i,j)$ 走到 $(i+1,k)$ 的最小距离。这个操作显然具有结合律，因此可以用线段树进行维护；每次单点修改，全局查询。

时间复杂度是 $O(n\log n)$，视 $n,q$ 同阶。