元の問題の解法を考えます。 実は以下のような性質があります。

\(A\) に 0 を追加してソートする。\([A_i, A_i+1) = [L, R)\) を考える。\(A_i\) を \(R\) 以上なら 1、そうでないなら 0 に置き換えた列に対する答えを \(T_i\) とする。 \(/sum_i T_i (A_{i+1}-A_i)\) が求める答え。

これは、適当な組み換えによって操作 2 で扱う区間がラミナーにできることから、最適解からボトムアップに列を構成できるため、従います。(ラミナーとは二つの区間が包含もしくは非交差の関係であることです。)

01 からなる列に対する答えは以下のような所謂「耳DP」と呼ばれるテクニックで解くことができます。

dp1:= 今、操作2の区間を選んでいる最中の時の最小値

dp2:=今、操作2の区間を選んでいない時の最小値

答えは明らかに \(N\) 以下なので、dp の値はその範囲で管理すれば良いです。つまり、dp の状態は \(O(N^2)\) 個しかありません。

問題の解法に移ります。 \(B\) を全てまとめてソートすることで、考えるべき区間 \(O(K^2)\) 個の答えを足し合わせます。 各 \(i\) について、変換した列で 0/1 になる数は前計算で簡単にわかるので、dp の状態を管理しながら順に計算すれば良いです。

計算量は \(O(K^2N^3)\) です。