一個目の区間和だけ絶対値を取る，という部分を無視して，単に区間に含まれる和の最大値が \(f(L,R)\) だった場合にどう解くかをまず考えます．

累積和をとって，適切に offset を調整すると，次のような問題になります．

• \(S(=2K)\) 個の長さ \(M(=N-K+1)\) の非負整数列 \(B_1,\cdots,B_{2K}\) がある． 各 \(1 \leq L \leq R \leq M\) について，\(\max_{L \leq i_1 \leq \cdots \leq i_{S} \leq R} \sum_{1 \leq k \leq S} B_{k,i_k}\) を計算し，全部足し合わせよ．

\(L\) を \(M,\cdots,1\) と動かしていきます． 固定された \(L\) に対して，\(dp[h][R]=\max_{L \leq i_1 \leq \cdots \leq i_{S} \leq R} \sum_{1 \leq k \leq h} B_{k,i_k}\) と定義します．

\(L\) を動かしたときの \(DP\) の値の変化に注目します． まず \(dp[1][*]\) について考えます． \(dp[1][L]:=B_{1,L}\) として，残りの \(dp[1][i]\) は chmax する操作ですが，chmax による差分を考えると，\(dp[1][*]\) に対する区間 add と見ることができます． この add については，足される値が非負で区間の左端は全部 \(L\) とすることができます．

この \(dp[1][*]\) の変化をうけて \(dp[2][*]\) も変化することになりますが，その変化の様子を見ると，これも区間 add (足される値が非負で区間の左端は全部 \(L\) )になります．

よってこの区間 add を管理することで，\(DP\) の値の更新が効率よく行えます．

以下，add の回数を見積もります．

\(dp[k][*]\) の値は常に広義単調増加です． そこで \(dp[k][i]<dp[k][i+1]\) となる \(i\) を変化点と呼ぶことにします． \(dp[k][*]\) に対する \(1\) 回の区間 \(add\) が \(dp[k+1][*]\) に対する \(1+a\) 回の区間 add に変わったとすると，\(dp[k][*]\) の変化点は \(a\) 個消えています． これを踏まえると，区間 add が起こる回数は全体で \(O(NK^2)\) であることがわかります．

変化点と差分を管理し，変化しない点を union-find でまとめるようにすると，\(O(N K^2 \alpha(N))\) 時間（\(\alpha(N)\) はアッカーマンの逆関数）の解法になります．

ところで，最初の区間については，区間和の絶対値をとっていたのでした． これにより，\(DP[1][*]\) を別の方法で更新する必要があります． しかし結局これも「足される値が非負で区間の左端は全部 \(L\) の区間 add」であることがわかります． よって同様に解くことができ，計算量も変わりません．

回答例(C++)

余談: この問題は \(N \times N\) Monge 行列 \(K\) 個の (min-plus) 乗算に帰着することができます． 各 Monge 行列の隣接差分をとると，\(O(N)\) 個の非ゼロ点が現れる構造です． このような行列の乗算は比較的高速に行えることが知られています（しっかりとサーベイしたわけではないですが \(O(N \log N)\) が現状最速だと思います）． これらを用いることで \(O(N K^2 \log (N))\) 解法が可能になるのですが，論文のテクニックを使用するだけで解けるという状態を避けるため，実行時間制限を厳しくし，\(O(N K^2 \alpha(N))\) 時間解法を想定解としています．