题解:设$f_{i,j}$表示到第$i$行,这一行的选择的矩形左上角为$(i,j)$的最大值,那么有$$f_{i,j}=S_{i,j+k-1}-S_{i,j-1}+S_{i+1,j+k-1}-S_{i+1,j-1}+\max_{l}\begin{cases}f_{i-1,l}-(S_{i,l+k-1}-S_{i,j-1}) \qquad l\in [j-k+1,j]\\f_{i-1,l}-(S_{i,j+k-1}-S_{i,l-1}) \qquad l\in [j,j+k-1] \\f_{i-1,l} \qquad \text{otherwise}\end{cases}$$把大括号里面的下标类别相同的项进行合并,设$x_{i,j}=f_{i-1,j}-S_{i,j+k-1}$ , $y_{i,j}=f_{i-1,j}+S_{i,j-1}$,上式变成$$f_{i,j}=S_{i,j+k-1}-S_{i,j-1}+S_{i+1,j+k-1}-S_{i+1,j-1}+\max_{l}\begin{cases}x_{i,l}+S_{i,j-1} \qquad l\in [j-k+1,j] \\y_{i,l}-S_{i,j+k-1} \qquad l\in [j,j+k-1]\\f_{i-1,l} \qquad \text{otherwise}\end{cases}$$使用线段树维护$f,x,y$三个值即可,每次重新build()+区间查询最大值即可。