いわゆるセグ木平面走査での解法です。

公式解説同様に座圧しておき、（高々）\(N\times N\) マス上の問題としておきます。

\(a_j\) (\(j ∈ \{0, 1, \dots, N-1\}\)) を「\(j\) 列目のマスたちに書かれた整数の総和」で初期化し、配列 \(a = (a_0, a_1, \dots, a_{N-1})\) を管理します。

ここで、\(i\) 行目のいずれかのマスを \((R, C)\) として（すなわち \((i, C)\) を）選んだときの \(S\) の最大値を、上記の配列 \(a\) を用いて求める方法を考えてみます。 \(i\) 列目のマスたちに書かれた整数の総和を \(b_i\) とし、\(b_i + \max_j a_j\) について考えます。これは、マス \((i, j)\) の整数が 2 回カウントされるときの総和になっています。

そこで、\(a_j\) を「\(i\) 行目を除く、\(j\) 列目のマスたちに書かれた整数の総和」になるように更新します。この状態で \(b_i + \max_j a_j\) を求めればよいです。

よって、\(i ∈ \{0, 1, \dots, N-1\}\) に対して上記の値を求め、それらの最大値が最終的な答えとなります。（\(i\) 行目についての処理をした後は、元々の \(a_j\) に戻すように更新しておきます。）

配列 \(a\) に対して行いたい操作は、「更新」「全体の最大値を求める」だったので、セグ木を用いて管理します。更新の処理と最大値を求めるのは \(O(N)\) 回なので、計算量は全体で \(O(N\log(N))\) 時間となります。

今回は \(i\) を順に見る必要はないですが、\(i\) を（たとえば）昇順に見ながら更新していくことで、二次元領域などに関するクエリを処理できる場合があります。

https://hcpc-hokudai.github.io/archive/structure_segtree_001.pdf pp. 47–58 などを見るとよいかもしれません。LIS や転倒数などが、平面走査で解ける基本的な例題です。