ABC429F

xzy090626 · 2025-10-27 11:07:34 · 题解

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

发现我们最终的轨迹中，一定是从左向右；因此可以合并每一列，只需要计算 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 同阶。