萌新看不懂题解求助

设 $f_{i, j}$ 表示第 $i$ 行填 $j$ 后，前 $i$ 行贡献的最大值。我们不考虑初始填过的数之间产生的贡献。

设 $c_{i, j}$ 表示第 $i$ 行中 $j$ 这个数的数量。为了美观，把 $c_{i, -1}$ 记作 $c_{i}$。

我们有两个转移：

确实，对于满足 $c_{i-1, j} = c_{i, j} = 0$ 的 $j$，即第 $i$ 行和第 $i-1$ 行都没出现的数，有转移：

如果记 $a = c_{i-1}c_i$，$b = \max\limits_{1\le t\le k} \left(f_{i-1, t}+c_{i-1}\times c_{i, t}\right)$，这些转移是 $x\gets \max(x + a, b)$，可以用线段树维护 dp 值。

但是怎么快速求 $b$ 啊？