解説
いろいろやり方はあるらしいですが、マージテクを用いる方法を解説します。
この問題の解はと
を辺で結んだときの
になります。
ということでまず最初にこれを愚直に求めてしまいましょう。
その後はクエリ毎にマージをしていきます。
マージをするさいに、小さい→大きいほうにマージすることで、全体ででできることが知られています
でマージするたびに、各整数が連結するかどうかをみていけば解がでます。
これはstd::setなどを用いてでできます。
よって全体の計算量はで求めることができました。
