[IOI2013] wombats

题意

太长略。

题解

很神的一题。

首先有一个naive的想法是每修改一次就跑一遍全源最短路，然后 \(O(1)\) 回答询问。
考虑到实际上可以优化，设 \(f_{i,j}\) 表示第一行第 \(i\) 个点到最后一行第 \(j\) 个点的最短路。
这题一个比较难想的一个点是考虑合并两个答案数组。

我们知道列数比较少，行数比较多，这显然是一个性质。
floyd 算法有一个很优的性质，就是可以合并两个答案数组，考虑一下操作就知道正确性。
知道了合并答案这个性质，就可以一行一行得往下推，这样做一次是 \(O(nm^3)\) 的。

合并两个答案 floyd 合并答案的过程显然是广义矩阵乘法，也就是满足结合律，考虑用线段树维护答案。

用 \(g(l,r,i,j)\) 表示从 \(l\) 行到 \(r\) 行的答案。
注意到有这样一个性质，\(g(l,r) = g(l,k) \times g(k,r)\)。
正确性显然，所以用线段树维护矩阵即可，时间复杂度 \(O(nm^3+qm^3logn)\) ，时间复杂度不可接受。

注意到这个矩阵乘法是具有决策单调性的，即转移 \(i\) 和 \(j\) 的决策点 \(p(i,j)\) 一定满足 \(p(i-1,j) \leq p(i,j) \leq p(i,j+1)\)

均摊下来做一次是 \(O(m^2)\)，很好，则现在的时间复杂度为 \(O(nm^2+qm^2logn)\)，时间复杂度可以通过。
注意到空间复杂度不可接受，考虑对线段树底层进行分块，将每一个块看做线段树的底层节点，在不爆空间的情况下块越小越好。
设块长为 \(B\)，时间复杂度 \(O(nm^2+qm^2log\frac{n}{B}+qm^2B)\)，code