去年末にやると言っていたんですが、やっと終わりました。 クエリで与えられた区間の最長増加部分列の長さを答えるやつで、計算量は \(\langle O(n\log(n)^2), O(\log(n))\rangle\) です。
実装前にイメージがつきにくかったのと、あったら楽しいかなと思ったので、ブラウザ上で可視化するおもちゃを作りました。
Range LIS Query を触って遊べるやつを公開しましたhttps://t.co/q4X7Oecddn pic.twitter.com/Hrw8Eq1wN5
— えびちゃん (@rsk0315_h4x) 2022年1月23日
ざっくりとした概要の解説も書きました。 実装の詳細などは書いていませんが、実装するために必要となるものの大まかな道筋を書きました。
ブラウザ上のおもちゃについては、どうせ描画パートが律速になるだろうと思ったので、計算量は \(\langle \Omega(n^2 \log(n)), \Omega(n^2)\rangle\) とかで動いていると思います。
