とりあえずTreapに区間和を載せて解いた。なんとなくややこしそうという先入観があったが、遅延更新がいらないので自明な変更で済んだ。
最初の投稿で1sec以上かかって平衡二分木は遅いなあと思っていたが、ボトルネックはパース部分だったらしく、応急処置的にparse-double-floatを書いたら350msにおさまった。これならぜんぜん問題ない。
以下、Treapに関するメモ。
- 簡単のために、あらゆるクエリに対して既存のキーを
deleteしてからinsertしているが、Treap中にキーがあればその値を更新し、無ければ挿入するという操作を作ったほうが良いかもしれない。（ensure-keyとか？） ただ、優先度は勝手に決められないので、走査を一度で済ませることはできない気がする。findして同じキーが見つかったら更新、見つからなかったら根に戻ってinsertするみたいな感じになりそう。 - この問題のように数値等以外の空間を対象にする場合は、演算のたびにコンシングが発生することになる。更新先のプレースを与えて結果をそこに保存する感じにすれば回避できそうだが、見通しが悪くなるのであまりやりたくはない。あるいは、オペレータを可変長変数にして
(op A (op B C))を(op A B C)に変えればコンシングが半分程度になる計算だが、それもやりたくない。仕組みは今のままで、必要ならopにコンパイラマクロを定義して(op A (op B C))を捕捉するくらいが落としどころか。 - もう少しTreapを使ったら、抽象的な実装を用意するかもしれない。現時点では次の2×2=4パターン（あるいは6パターン）あれば十分に見える。
- explicit key, implicit key
- 一点更新区間取得、区間更新区間取得、（機能なし）
