まず \(O(N^2)\) の DP を考えます． 数列の要素を先頭から \(1\) つずつ見ていって，\(2\) つの部分列の一方に追加する，という手順を考えます． \(B_i=\min\{A_1,\cdots,A_i\}\) とすると，部分列の一方の \(\min\) は \(B_i\) となっています． よって，\(\min\) が \(B_i\) でない部分列の \(\min\) をキーとして，その時点での \(f(X_1)+f(X_2)\) の和の最大値を保存する DP が考えられます．

\(A\) をソートした結果を \(V=(V_1,\cdots,V_N)\) とおきます． この DP の遷移を眺めると，以下の操作に帰着されます．

• 区間 add
• 区間 getmax
• ある区間について，区間内の \(i\) に対して \(dp[i]\operatorname{+=}V_i\) とする

最初の \(2\) つの操作は lazy segtree で処理できますが，最後の操作が難しそうです．

これは segtree beats で処理できます． 特にこの処理を行う segtree は一部で kinetic tournament という名前で呼ばれています． ここでは大雑把なアイディアを解説します．

まず，segtree の各ノード \(x\) に，そのノード内の DP 値の max \(W_x\) を保存しておきます．\(W_x\) に対応する \(V_x\) も保存しておきます． ノード \(x,y\) (\(x,y\) はこの順に左右に並ぶ)をマージし，ノード \(z\) を作ることを考えましょう． ここで，max がノード \(y\) から来る(つまり \(W_x \leq W_y\)) だったとします． このノード全体に \(dp[i]\operatorname{+=}V_i\) の操作を行ってみます．すると，操作後においても \(W_x \leq W_y\) が成立しています． よって，このノード全体への操作は，ノード \(y\) への操作に帰着されるので，簡単に処理できそうです．

\(W_x > W_y\) だった場合はどうなるでしょうか？ この場合は，このノードに \(t=(W_x-W_y)/(V_y-V_x)\) 回以上の操作が来たタイミングで，\(W_x,W_y\) の大小関係が入れ替わることになります． そこで，大小関係が入れかわるタイミングを各ノードに保存しておくことにします．

ところで，\(W_x,W_y\) の大小関係は変わらないが，ノード \(x,y\) 内で max を取る場所が変わってしまう，というケースがあります． これを処理するためには，各ノードに対し，「そのノードの部分木内で大小関係が入れ替わる最短のタイミング」を保存しておけばよいです． ノード \(z\) に更新が来た際は，\(z\) の部分木内で大小関係が変わるノードがあるなら更に深く潜り，ないなら \(z\) にある情報だけで更新する，という処理を行えばよいです．

以上のアルゴリズムの計算量を見積もります． まず各ノード \(z\) について，\(W_x,W_y\) の大小関係が入れ替わる回数を考えます． 一度 \(W_x\leq W_y\) が達成されたあと，再び \(W_x>W_y\) となるためには，ノード \(z\) を”カット”するような操作が必要です． segtree に対する区間クエリ \(1\) 回につきカットされる区間は \(O(\log N)\) 個なので，全体で \(O(N \log N)\) 回の入れ替わりが発生します． 一回の入れ替わりにつき，segtree のノードを \(\log N\) 段潜る必要が発生します． よって計算量は合計で \(O(N \log^2N)\) になります．

回答例(C++)