Joeさんの実装で、pushdown中でpushupが必要な理由がわからなくてずっと悩んでいた。この実装ではpushdown→子に降りる→…→戻ってくる→pushupというふうに常にセットで呼んでいるし、accの値は子には影響しないのだから、pushupでaccを更新するのは戻ってきたタイミングだけで十分に見える……のだが、自分の実装(Common Lisp)でpushdown中のpushupを消すと正しく動かない。 しかし、ようやく解決した。結論から言えば、
- Joeさんの実装では（たぶん）
pushdown中のpushupはいらない。とりあえずAOJ DSL_2_HとAOJ 1508では確認済み。 - 手元で正しく動かなかったのは、自分の実装がバグっていたから。
結果は平凡だが、遅延更新Treap（merge/splitベース）の実装のポイントがわかったのが収穫だった。
- すべての操作は、
acc、lazy、value等が全体として整合的になっているTreapを返さなくてはならない。これは当然。 - それに加えて
merge/splitの返すTreapの根(top)は評価済みでなくてはならない。 つまり、根に限ってはlazyやrevが解消されてaccが正しい値になっている必要がある。merge/split以外の操作についても、常にこれを守ったほうが余計なことに気を配らずに済むと思う。 - また、
merge/split自身は根が未評価のTreapを正しく扱えなければならない。
という感じか。
上の原則が守られていれば、update中のt2->acc = Modifier::op(t2->acc, x, cnt(t2));はいらないはず。（mergeはlazyが0でない根を適切に処理するので。これも確認済み。）
そのうち報告するかもしれない。でも別にバグではないので……
とりあえず、自分の実装はこれ。区間更新区間取得と１点更新区間取得があるのだが、本当は１つにまとめられるはずだ。抽象化はもう少し使ってみてからにしたい。
