yukicoder No.1170 Never Want to Walk
はじめに
問題が全体的に実装軽めで面白かったです。
想定解を思いつきはしたんですが、「区間のマージやりたくない…」と思って捨ててしまいました。 imosとか使えば普通に出来るんですけどね…
考察
区間に辺を張ることが出来ればよいことが分かります。
ここで、熨斗袋さんの区間に辺を張るテクのツイートを思い出すと解けます。
参考
セグ木の形にして区間に辺を張るテク
— 熨斗袋 (@noshi91) 2019年11月9日
頂点 +N 個
辺 +N+ElogN 個 pic.twitter.com/Xrw5y9bq2Z
セグ木っぽくしたほうが早いんですが、実装が面倒だったので平方分割で書きました。
想定のほうが実装も計算量も軽いです。
実装の軽い説明をすると、[0,n)は頂点の頂点、[n,n+sqrt(n))を区間の頂点にしてunionfindをしています。 最後に集合に含まれる区間の数を答えから引いてやる必要があります。
