遊園地(みんなのプロコン 2017 [E]) AtCoder 2022.05.11 スポンサーリンク 目次 概要解法 概要 問題文 → ■公式解説 → ■自分の提出 → ■ 公式解説も面白いけど、こっちの方が分かりやすいかな? 解法 解説同様に、次のように辺を張ったグラフを作って強連結成分分解すれば解くことができます。 i<j かつ Ri+i≧Lj+j のとき、i→ji<j かつ Li−i≦Rj−j のとき、j→i 分割統治で解きます。区間 [l,r) に対する処理は、m=⌊(l+r)/2⌋ とするとき次のようになります。 [l,m), [m,r) 内での辺を再帰的に張るm をまたぐ辺を張る m をまたぐ辺、つまり [l,m) と [m,r) の間の辺を張るのですが、この部分について上手く辺の本数を減らせればよいです。 i→j 型の辺のみ説明します。[l,m) 内の頂点を昇順に並べて v1,…,vm−l とすると、各 j に入る辺を張る操作は「ある k に対して、vk,vk+1,…,vm−l から j に辺を張る」という形で表せます。これは、vi+1 から vi に辺を張っておくことで、ひとつの辺で表現できます。 分割統治において、長さ n の区間に対して O(nlogn) 時間で O(n) 本の辺を持つグラフを構築します。したがって、全体の計算量は O(nlog2n) 時間、グラフの大きさは頂点・辺の数とも O(nlogn) となります。