X - 不揃いさ/Unevenness 解説
by 
Nyaan
この問題はフローをセグメント木を用いて高速化するテクニックを利用する問題です。 (maroon さんがコンテストのボス問に 2 回ほどこの種の問題を出題したことから、俗に maroon 典型 と呼ばれることもあります。)
まず、目的関数は費用流双対と呼ばれる問題であることが確認できます。(費用流双対は ABC393-G の解説に非常に詳しく書かれているのでこちらを参照してください。)
よって実数緩和して LP 双対を取る操作が正当で、双対を取ると答えは以下の手順で構成されるグラフの最小費用循環流のコストを \(-1\) 倍したものになります。(双対の取り方も上記の解説記事に詳しいです。)
- 超頂点 \(S\) および頂点 \(1, 2, \dots, N\) からなる \(N+1\) 頂点のグラフに以下の手順で辺を貼る。
- \(1 \leq i \leq N\) について頂点 \(S\) から頂点 \(i\) に容量 \(g_i\) 、コスト \(-A_i\) の辺を貼る。
- \(1 \leq i \leq N\) について頂点 \(i\) から頂点 \(S\) に容量 \(g_i\) 、コスト \(A_i\) の辺を貼る。
- \(1 \leq i \leq N-1\) について頂点 \(i\) から頂点 \(i+1\) に容量 \(d_i\) 、コスト \(0\) の辺を貼る。
- \(1 \leq i \leq N-1\) について頂点 \(i+1\) から頂点 \(i\) に容量 \(d_i\) 、コスト \(0\) の辺を貼る。
上記の最小費用を、\(A_i\) の変更に対応して随時計算できればよいです。
想定解では、\(A_i\) の更新を \(\mathrm{O}(Q)\) 回の容量 \(1\) の辺の追加と削除に言い換えています。
まずはその理由を説明します。\(A_i\) を変更すると、\(S \to i\) と \(i \to S\) のコストだけが変わります。そこで、この \(2\) 本の辺を一旦削除し、\(A_i\) を変更してから、新しいコストで追加し直すことを考えます。容量 \(g_i\) の辺は同じコストを持つ容量 \(1\) の辺 \(g_i\) 本とみなせます。\(g_i \leq 2\) なので、\(1\) 回のクエリで追加・削除する辺の本数は定数となります。
現在のグラフを \(G\)、その最小費用循環流を \(f\)、残余グラフを \(G_f\) とします。\(f\) が最適であることは、\(G_f\) に負閉路がないことと同値である点に注意してください。容量 \(1\) の辺 \(e\) の追加・削除は、次のように処理します。
- 辺 \(e\) の追加：\(G_f+e\) において、\(e\) を含む閉路のうちコスト最小のものを求める。そのコストが負なら、その閉路に沿って \(1\) 流す。負でなければ何もしない。
- 辺 \(e\) の削除：\(e\) の流量が \(0\) なら、そのまま削除する。流量が \(1\) なら、\(e\) の逆辺を含む閉路のうちコスト最小のものに沿って \(1\) 流して、\(e\) の流量を \(0\) に戻してから削除する。この場合は、閉路のコストが非負でも流す必要がある点に注意する。
詳しい説明については ABC363-G の公式解説や maspy さんのユーザ解説で証明付きで行っているのでそちらを参照してください。
最後に、このグラフの形を利用して、閉路の探索と流量の更新をセグメント木で高速化します。 考える閉路は \(S \to i \to \cdots \to j \to S\) という形で、\(i\) と \(j\) の間はパス上を移動します。 パス上の辺のコストはすべて \(0\) なので、この閉路のコストは \(A_j-A_i\) です。
まず、パス上の各辺の右向き・左向きの容量を、区間加算・区間最小値を扱える遅延セグメント木 \(2\) 本で管理します。 頂点 \(i\) からパス上を移動できる範囲は、左右それぞれで、進む向きの容量が \(0\) となる最初の辺までの連続区間です。 「区間の最小容量が正」という条件でセグメント木上の二分探索を行えば、この範囲を \(\mathrm{O}(\log N)\) で求められます。
さらに、各頂点 \(j\) について、辺 \(j \to S\) が使えるなら \(A_j\)、使えなければ \(+\infty\) を載せた、区間最小値用のセグメント木を用意します。 到達範囲内で \(j \ne i\) を満たす頂点の最小値とその位置を求めれば、辺 \(S \to i\) を使う最小コストの閉路が見つかります。 辺 \(i \to S\) を使う場合は、\(j\) から \(i\) に到達できる範囲を調べ、\(S \to j\) が使える頂点の \(-A_j\) の最小値を、もう \(1\) 本のセグメント木で求めます。 この場合は、左右それぞれで調べる容量の向きを反対にする必要がある点に注意してください。
閉路に \(1\) 流すと、パス上では通る区間の容量が、流す向きに \(-1\)、逆向きに \(+1\) 変化します。これは区間加算で処理できます。 \(S\) と接続する辺の容量が変わるのは頂点 \(i,j\) だけなので、頂点のコストを管理するセグメント木は一点更新で処理できます。
したがって、閉路の探索と更新は定数回のセグメント木に対するクエリで処理できて、容量 \(1\) の辺の追加・削除をそれぞれ \(\mathrm{O}(\log N)\) で処理することができました。
以上の内容を適切に実装することで、この問題を \(\mathrm{O}((N + Q) \log N)\) で解くことが出来てこれは十分高速です。
類題
類題は様々な場所で出題されています。練習にお使いください。