CF 373 div2

まだジャッジ終わってないけど反省文だけ書く。
A, B, Cはどれも線形オーダーの実装ゲーだった。
Aはhackされてて書き直しても落ちて笑った。
コーナーケースわからん。

B, Cはpreは通ったが落ちるかも。こういう問題コーナーケース対処が本質みたいなとこあるのであんまり好きじゃない。
Dは解いた人数が少なかったので無視した。前処理+二分探索系だと思うけどよくわからないし実装も難しそう。
EはDの倍以上解かれていたので簡単なのかなと思って見てみたらフィボナッチ数列を範囲addセグツリーで管理するみたいな問題で、なるほど慣れている人は速いだろうな、と思った。範囲addタイプのセグツリーは何度かコンテストの解説で見たことがあるだけで書いたことは一度もない。適当にネットで検索して出てきたのを真似して書いてみたが、数列の和と数列の和を持っててもこれ合成できないじゃん、というかフィボナッチ数列をいちいち行列累乗してて間に合うのかなと思っているうちに終わった。上位の人の解答を見ると、そもそも行列を持ってセグツリーを構築しているし、フィボナッチ数列はlogMAX_V(1e18)くらいまでをあらかじめ繰り返し二乗法で計算していた。なるほど、とは思うがこんなの実装できる気がしないなあ。繰り返し二乗法の応用みたいの（ダブリング的なやつ）わりとよく出るんだけど、いつも実装できる気がしないと思って復習せずにあきらめてしまう。なかなか初心者脱却できない要因がこのへんにある気がするので、今回はちゃんと復習してみようかな。

[追記]
こどふぉのblogを見ていたらなんかDiv1B(Div2D)のwriter解がアレでunratedになるかもと書いてあった。
ついでにセグツリーの練習問題（というか、ライブラリチェック用？）
http://www.spoj.com/problems/SEGSQRSS/
を拾った。あとでやろう。
[さらに追記]
ratedになっててビビった。あとDが消えてた。赤コーダー数人が点検しても想定解の間違いを見抜けない問題、闇が深いなあ。