最近競プロを再開した。
とりあえずAtCoderの過去問をひたすら解いているのだけど、以前よりも沢山の問題が解けるようになっている気がする。
ここ数年間はあまり脳を働かせていなかったので衰えているかと思ったけど、そうでもないみたいだ。
といっても、1日かけても解けない問題もちらほらあり、昨日は双対セグ木の考え方を用いた方法が想定解である問題を解こうとして、解けなかった。
この問題から学んだことをどうしても書き残したいと思い、今回の記事を書いている。
というのも、双対セグ木、もう少し抽象化した完全二分木は、頂点数が O(N) である。
そして、そのうち半分の頂点は区間の情報を持つ。
範囲に対する更新操作を行ったとき、その操作の大半は各要素ではなく区間に対して行われるため、これにより保有している情報が変更される頂点の数は高々 logN 個程度である。
これは、たとえば各頂点がmultisetを持ち、範囲 [0, N) に対して A←max{A, x} という操作を Q 回行ったとしても、空間計算量が O(QlogN) 程度に収まるということである。
一度の更新操作ですべての頂点のmultisetが更新されることはない。
よって、multisetなどの「操作回数に応じてメモリ使用量が増えるようなデータ構造」を各頂点に持たせても問題はない。
問題を解いているときはこの事実に気付かなかった（「頂点にmultisetやpriority_queueを持たせるのは良くない」と思い込んでいた）。
この気付きは自分にとって大きいものだったので今回は書き残した。
