\(N\leq 10^{12}\) という制約に注意して，事前に座標圧縮しておきます．

\(x\mapsto ax+b\) の形の変換はアフィン変換と呼ばれます．その全体は合成で閉じており，モノイドをなします．

したがって，セグメント木でアフィン変換の列を管理すると，\(1\) 点でのアフィン変換の変更と，全体での合成の計算を高速に行うことができます．

よって各時点での美味しさが計算できるので，それらをすべて計算して最小値・最大値を出力すればよいです．

座標圧縮に \(O(M\log M)\) 時間，セグメント木の基本操作に 1 回あたり \(O(\log M)\) 時間でできて，全体として計算量 \(\Theta(M\log M)\) で解くことができます．

解答例：https://atcoder.jp/contests/arc008/submissions/42112486