ARC008 D - タコヤキオイシクナール (100)
セグ木になれるためにセグ木が使える問題を解いてみた。
テンプレートを使っているのである程度汎用性のあるライブラリになってくれるはず。
セグ木の中で上に行くにつれてaとbを合成していく
すべてのボックスを通るのでqueryは常に$ [0,m)に対して行われる
トンネルを通る前の1も答えの候補になるので、最小値最大値共に1で初期化できる
求めるのは$ 合成されたa \times r + 合成されたbで初期値は$ r = 1
なので、各クエリでの答えはセグ木の0番目の要素の$ a + bになる