[問題案] Point Set Range Composite (Linear Functions) (point_set_range_composite)

[yosupo06]

問題概要

• 問題ID: point_set_range_composite
• 問題名: Point Set Range Composite (Linear Functions)

1次関数、1点変更 / 区間関数合成

N個の一次関数f_0, f_1, ..., f_{N - 1}が与えられる。f_i = a_i x + b_i。Q個のクエリを処理

• 0 p c d: f_p(x) = (cx + d)に変更
• 1 l, r, x: f_r(f_{r-1}(...f_{l+1}(f_l(x))...)を出力

全てmod 998244353

入力

N Q
a_0 b_0
a_1 b_1
:
a_{N - 1} b_{N - 1}
query 0
query 1
:

制約

N, Q <= 500,000
0 <= 値 < 998244353

[yosupo06]

• 名前をどうするか(Fenwick Treeをpoint_add_range_sumにしたが、これと対応づけられる気がしないなァ)

• 合成の向きをどっちにするか

[yosupo06]

f_r( ... ( f_l(x) )..)の方向の合成が自然でしょう

[yosupo06]

(adhocにやればa=0でも逆元があるかのように扱えるはずだし)逆元消す理由がないので0<a

[yosupo06]

#183