解法
簡単なバージョンで問題を考える． \(i \in N\) 毎に独立に解けるので，\(N=1\) として考える． \(y := A_{0}\) とおく． \(j \in [0,M]\) に対して，
\(y_{j} := \) \([0,j)\) まで終えたときの \(y\) の値の期待値
とする．
遷移を求める． \(x_{j+1}\) は， 確率\(p := \frac{1}{r-l}\) で \(x_{j}\) になり， 確率\*1;
AtCoder Beginner Contest 332F問題
tr.apply(l,r,f);
}
rep(i,n){
cout << tr.get(i).val() << endl;
}
return 0;
}
*1:q := 1-p\) で \(y_{j}\) のままである． よって遷移は $$ y_{j+1} = q y_{j} + px_{j} $$ となる．
実装
\(a,b \in \mathbb{Z}\) に対して， 写像 \(f: \mathbb{Z} \rightarrow \mathbb{Z},\ x \mapsto ax + b\) の全体 \(F\) を考える． 作用素 \(F\) とモノイド\((\mathbb{Z},\ +)\) に対して 遅延伝搬segtree を使えばよい．
注意
モノイドの演算は使わないので，別の演算でも代用できるかも．
使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"
int main() {
ll n,m;
cin >> n >> m;
vll a(n); rep(i,n) { cin >> a[i]; }
lazy_segtree<S,op,e,F,mapping, composition, id> tr(n);
rep(i,n){
tr.set(i, a[i]);
}
rep(i,m){
ll l,r,x; cin >> l >> r >> x;
--l;
S p = mint(1)/mint(-l+r);
S q = mint(1) - p;
F f(q, p*mint(x
