ARC008 D. タコヤキオイシクナール

問題

ベルトコンベアにN個のトンネルが一直線に並んでいる。
トンネルには実数のペア(a,b)が書かれており、おいしさrのタコヤキがそのトンネルを通ると、おいしさがa*r+bに変化する。
最初はトンネルの実数のペアはすべて(1,0)になっているが、M回トンネルの一つを選びその実数のペアの値を変更する。
各変更によって、おいしさ1のタコヤキがすべてのトンネルを通った後においしさがどうなるか知りたい。おいしさの最小値と最大値を求めよ。

制約

• 1 <= N <= 10^12
• 0 <= M <= 100,000
• -1.0 <= 変更後のa,b <= 1.0

解法

セグメント木はモノイド(二項演算と単位元)に適用でき、

• 二項演算(2つのトンネルを連結させる)
  • 「x -> (a,b) -> (c,d) -> ?」は「x -> (a*c,b*c+d) -> ?」にできる
• 単位元
  • (a,b)=(1,0)

と考えればよい。

非可換な二項演算なので、以下の「Non-commutative combiner functions」を参考にセグメント木を作ればよい。
Efficient and easy segment trees - Codeforces

変更が行われた後は、すべてのトンネルを通った後の結果を知りたいので、セグメント木のルートノードの情報を使えば求められる。

Nが大きいが、Mが小さいので、あらかじめ与えられる変更情報に含まれないものは無視(座標圧縮)しておけばよい。