[問題案] Range Set Range Composite

[SSRS-cp]

問題名: Range Set Range Composite

問題

N 個の一次関数の列がある。Q クエリ

0 l r c d: f_l, f_{l+1}, ..., f_r を cx+d に変更
1 l r x: f_r(...f_{l+1}(f_l(x))...) mod 998244353 を出力

制約

#122 と同じ

メモ

これ必要か？必要ないかもしれません　意見を募集します
想定は これ です (通常の遅延セグ木だと累乗の計算が必要なため log が 2 つついてしまう)

[maspypy]

log が落ちるならあってもよいと思います。
テストケース作りを少し工夫しないと、普通の遅延セグ木と速度差が出にくいかもしれません。

[maspypy]

作業者募集。

[maspypy]

ところで、別解法。こっちの方がよく見る処理かも。

• 列をいくつかの定数区間に分けて管理
• $[a,b)$ を $[a,x)$ と $[x,b)$ に分ける / いくつかの区間をまとめてひとつの定数区間で置き換える / いくつかの定数区間の積をかける、をやる。
• segtree + set などでできる

[NachiaVivias]

それが verify できるの便利そうですね。

作業します。