0.1%の確率で更新を怠るセグメント木
こんばんは。最近実装力に自信がなくなってきているheno239です。
タイトル通りですが、今回は0.1%の確率で更新を怠るセグメント木を実装しました。ソースコードはこちらです↓
gist072edeb5ab1fd40f73fbeb6a2fc01dd7
作っただけじゃ面白くないので、更新を怠らない真面目なセグメント木と比べてみました！
今回の比較では、非常にシンプルな練習問題として
Range Minimum Query (RMQ) | Aizu Online Judge
を用いました！
以下が比較実験の結果となります！
-
真面目なセグメント木
当たり前ですが、通ります。
-
サボる方のセグメント木
いい感じにWAになります。
-
まとめ
いかがだったでしょうか？
ちなみにこの0.1%の確率で更新を怠るセグメント木の使い道についてですが、
-
1.運試しに用いる
-
2.最近ACばっかりでつまらない時や、意味もなくWAを出したくなった時に用いる
-
3.ライバルのライブラリにこっそり忍び込ませ、WAを連発させて蹴落とす
などが考えられます。いずれにしても何かを失う可能性があるので、ご利用は計画的に。それでは。
