解法構築

JOIでよくある、"〜法を発明しなさい"みたいな問題

知らない状態で最小全域木問題が出されて、Kruskal法を発明せよと言われてる感じ

この問題は、非内包-外包関係の区間に辺を張ったグラフの成分数を求める問題

部分点2(22pt)

問題文を読むと、問題が分かるので、それを実装する、O(N^2)

天才的な数えかたはできそうにないので、連結性の等しい部分グラフ（木に近いと望ましい）を構築する必要がある

定石通り全順序に従って走査していくことを考える

左端の昇順に頂点を追加していくと、右端の大小関係だけが辺の有無に関係することがわかる

具体的には、左端[今]より大きい右端[昔]に対して、右端[今]より小さいものに辺が張られる

計算量を削る唯一の現実的な手段は、同じ成分に何本も辺を伸ばさないことである

逆にそのようにすれば、構築するグラフは木となり、オーダーが落ちる

ここで、非内包-外包関係の区間どうしに辺を張っていることから、成分は内包-外包関係の区間に表される

走査中は区間内包の木は分岐しない線になるから、同じ成分の右端は連続する

この性質により、成分の扱いがしやすくなる

注目している頂点とある成分の間に辺があるとは、成分内最左 | 左端[今]より大きいの頂点が右端[今]より小さいことである

よって、成分の最左頂点の順序集合を管理していくことを考える

左端[今]に達した頂点は消す必要があり、その頂点の成分の、次に小さいものがわからなければならない

通常ならば各成分で順序集合を持って、それどうしをmergeする必要があって間に合わないが、今回の頂点集合は成分どうしで順序が明らかである

片方の成分の頂点はもう片方の成分の頂点より必ず小さい

mergeが区間どうしの連結のみによって表され、これはListを使って定数で可能

pop,uniteがO(1)ででき、pop,uniteの回数は両者共に合計O(N)だから、オーダーは順序集合の扱いがボトルネックとなるまでに落ち、O(NlogN)

Setで二分探索をしたので定数倍が重い

AGCは人工建造物みたいだったけど、これは天然の要塞みたいな感じで面白い

この問題は最初から最後まで全順序に従っていれば解けた

適当な考察でペナルティ77を出した