普通の segment tree で解くことができます。

\(i=1,2,\dots N\) について以下の \(2\) つの値が求まれば良いです。

• 一度も変更されない確率
• はじめ、\(A_{i}=0\) であったときの最終的な \(A_{i}\) の期待値

\([a,b)\) の区間の操作での上記の値をそれぞれ \(pro_{l},val_{l}\)、\([b,c)\) の区間の操作での上記の値をそれぞれ \(pro_{r},val_{r}\)としたとき、 \([a,c)\) の区間での操作での上記の値は以下のようになります。

\(pro=pro_{l}* pro_{r}\)

\(val=val_{l}*pro_{r}+val_{r}\)

よって、この \(2\) つの値は segment tree に載せることができます。

あとは平面操作をすれば \(O(N+M\log(M))\) で解くことができます。

具体的には、 長さ \(M\) の上記の \(2\) つの値をもつ構造体を要素とした segment tree を持ち、\(j\) 番目の要素が \(L_{j}\leq i\leq R_{j}\) なら \((1-\dfrac{1}{R_{j}-L_{j}+1},\dfrac{X_{j}}{R_{j}-L_{j}+1})\) 、そうでないなら \((1,0)\) とすることで、上記の \(2\) つの値は区間全体を取ることで求めることができます。愚直に見ると \(O(NM)\) かかりますが、\(i=1,2,\dots N\) の順番に見ると、segment tree の \(j\) 番目の要素が変更される回数は高々 \(2\) 回なので、計算量を抑えることができます。

ACL を用いた C++ の実装例