洛谷链接 https://www.luogu.com.cn/problem/P9014
首先，我们可以从题目中发现一个性质和一个优化计算的小技巧。
设 $go_{i,j}$ 为第 $i$ 行 $j$ 列的路标状态，则维护牛到达某个点的个数 $cnt_{i,j}$ 代码如下：
得到了 $cnt$，我们就可以用 $\mathcal{O}(n)$ 的时间复杂度统计答案了。
那么，问题又来了——怎样实现修改？其实很简单：我们知道，get_ans() 函数依赖于 $cnt$ 的数据。也就是说，只要我们改变了 $\bm{cnt}$ 的数据，使其成为修改路标过后的数据，就可以 $\mathcal{O}(n)$ 获取答案了。那么，现在就要用一种方法，使得 $cnt$ 的修改为 $\mathcal{O}(n)$ 而不是 $\mathcal{O}(n^2)$。
事实上，对于这个问题，还有一个很明显的性质：当我们修改点 $(i,j)$ 时，只有经过 $\bm{(i,j)}$ 的牛才会被影响。容易发现，经过 $(i,j)$ 的牛为 $cnt_{i,j}$ 个。现在路标改变了，那 $cnt_{i,j}$ 头牛原本从 $(i,j)$ 出发的路径就不再经过了，那么这条路径上的 $cnt$ 值都得减去 $cnt_{i,j}$，因为这 $cnt_{i,j}$ 头牛都不会再经过这条路径了。而且，在路标改变后，新的从 $(i,j)$ 出发的路径上的 $cnt$ 值又会增加 $cnt_{i,j}$。仔细想想，从 $(i,j)$ 出发最多只会走 $2n$ 次！即使从 $(1,1)$ 出发，走过的路标都是右下交替，最多也只会走 $2n$ 次。所以说，暴力修改 $cnt$ 是线性复杂度！那么，按照上述内容模拟一遍就可以了。