セグメントツリーを使う.

区間内の総和を \(s\), 左端を含む区間の総和の最大値を \(t\), 右端を含む区間の総和の最大値を \(u\), 区間内の総和の最大値を \(v\) とする. この \(s, t, u, v)\) の合成を考える. これは左側に \(l\), 右側に \(r\) の添字をつけて考えると,

\[\begin{align} s &= s_l + s_r \\ t &= \max(t_l, s_l + t_r) \\ u &= \max(u_r, u_l + s_r) \\ v &= \max(v_l, v_r, u_l + t_r) \end{align}\]

と合成できる.

クエリ \(l_1, l_2, r_1, r_2\) が与えられたときに以下の問い合わせをセグメント木に行えば答えが求まる.

\(l_2 \lt r_1\) のとき:

\[u[l_1, l_2] + s[l_2, r_1] + t[r_1, r_2] - a_{l_2} - a_{r_1}\]

\(l_2 \geq r_1\) のとき:

\[\max \{ u[l_1, r_1] + t[r_1, r_2] - a_{r_1}, u[l_1, l_2] + t[l_2, r_2] - a_{l_2}, v[l_2, r_1] \}\]