tayu0110 / tayu-procon

My Competitive Programming Library
Creative Commons Zero v1.0 Universal
1 stars 1 forks source link

SegmentTree : 左右畳み込みメソッドを両方用意する #14

Open tayu0110 opened 1 year ago

tayu0110 commented 1 year ago

yosupo judgeのPoint Set Range Compositeはセグ木で解く場合は右畳み込みができないと解けないが、今の実装では左畳み込みでしか実装されておらず、右畳み込みが必要な問題にぶち当たると死んでしまう。 なので、左右両方向からの畳み込みを用意する必要がある。 Haskellにfoldl, folrみたいな感じの名前の関数があったと思うので、そんな感じの名前でいいと思う。 左右畳み込みの方向、今認識している通りで合ってたっけ…要確認。(今は、右に向かって値を集めていくようなものを右畳み込みと認識している)

tayu0110 commented 1 year ago

一応できたが、あまり使いやすいとは言い難い感じになった。 verifyはすんでいるので、使える状態ではある。 とりあえずしばらく使ってみてから必要があれば改良。 しばらくissueはクローズせず残しておく。