読者です 読者をやめる 読者になる 読者になる

ctyl's problem solving

競技プログラミングが主な話題です。

yukicoder No.259 セグメントフィッシング+

yukicoder

BIT★4.BITを学んだ後に解く問題でBITやるだけ,では物足りない方にはオススメかもしれません.

右向きに場所{0,1,\cdots,N-1}で泳ぐマスと左向きに場所{N-1,\cdots,1,0}で泳ぐマスを連結させ長さ{2N}のBITを用意する.LコマンドやRコマンドに相当する挿入は{t = 0}のときどこにいるかを計算する.Cコマンドでは指定する範囲がBITでは両端を含むような時があることに注意すること.もちろん右向きと左向きがあるので最低でも指定する範囲は2つある.

No.259 セグメントフィッシング+ - yukicoder

yukicoder No.259

最近は木構造をAOJなどでやっています.画像処理とかで使うようなアルゴリズムもあるので,教養として抑えておきたい部分もあるかも.(本当は学部時代にやっておくべきなのですが・・) RMQなども記事化できるといいなあ(わかりやすいreferenceがたくさんあるのもあってなかなか記事にするモチベーションが)