まずは簡単な例として、実数 \(x\) を決めたときに「答えが \(x\) 以上になる確率」を求めてみます。

実数 \(x\) に対し、「\(i\) 番目の変数まで見て、\(x\) 以上の値がちょうど \(j\) 個になる確率」を\(dp_x[i][j]\) とします。\(x\) を固定したとき、各 \(i\) について \(X_i\) が \(x\) 以上になる確率は \(O(1)\) で求めることができるため、このDPテーブルは \(O(N^2)\) で埋めることができます。「答えが \(x\) 以上である確率」は \(\sum_{j=K}^{N} dp_x[N][j]\) となります。

本題に戻ります。

「答えが \(x\) 以上になる確率」を \(F(x)\) とおくと、求める答えは \(-\int_{\min(L)}^{\max(R)} xF'(x)dx\) です。（Fが上側累積なので符号に注意）

さて、計算式をよく考えると、\(F\) は区分的に多項式であることがわかります。すなわち、\(x\) を変数としたままこのDPテーブルを埋めることを考えると、\((L\cup R)\cap(l,r)=\emptyset\) であるような区間 \([l,r]\) について、\(dp_x[i][j]\) は \(x\) の多項式として一定です。

\(\#(L\cup R)\leq 2N\) なので、高々 \(2N\) 個の区間に分割して考えればよいです。区間を固定するごとに、\(dp_x[i][j]\) は \(i\) 次の多項式であることから、DPテーブルは \(O(N^3)\) で埋めることができ、計算量は全体で \(O(N^4)\) となります。

実装例(Python)

多項式を持つDPが面倒であれば、適当な値 \(x\) に対して何度かDPして \(F(x)\) を求めた後、多項式補間で \(F\) を求めてもよいでしょう。この場合も計算量は \(O(N^4)\) となります。この解法はDP部分をFFTに置き換えることで \(O(N^3 (\log N)^2)\) にもなります。(詳細略)

実装例(C)

更に良い計算量でこの問題を解くこともできます。

\(x\) が別の区間に移るとき、dpテーブルを全て計算し直すのではなく、差分だけ更新すると全体で \(O(N^3)\) で求めることができます。これは「戻すDP」と呼ばれるテクニックですが、以下のように多項式で理解すると容易でしょう。

\(p_{i,x}\) を確率変数\(X_i\) が \(x\) 以上の値になる確率とします。このとき、\(X\) を不定元とする \(N\) 次多項式 \(G_x(X):=\prod_{i=1}^{N}((1-p_{i,x})+p_{i,x}X)\) の \(k\) 次の係数は \(dp_x[N][k]\) に一致します。したがって、DPテーブルの代わりに \(G\) を考えて良いです。\(x\) が変化したとき、\(p_{i,x}\) が (\(x\) の多項式として) 変化する部分についてのみ計算し直すことは \(O(N^2)\) でできます。

具体例としてサンプル2を考えます。

\(0\leq x \leq 1\) のとき、\(\displaystyle p_{1,x}=\frac{2-x}{2}\)、\(p_{2,x}=1\)なので、\(\displaystyle G_x(X)=\left(\frac{x}{2}+\frac{2-x}{2}X\right)\left(0+1X\right)=\frac{2-x}{2}X^2+\frac{x}{2}X\) となります。
\(1\leq x \leq 2\) のとき、\(\displaystyle p_{2,x}=\frac{3-x}{2}\) と変化するので、\(\displaystyle G_x(X)=\left(\frac{2-x}{2}X^2+\frac{x}{2}X\right)\div \left(0+1X\right) \times \left(\frac{x-1}{2}+\frac{3-x}{2}X\right) = ...\) と計算できます。
第1項が「\(x\) の高々 \(N\) 次式を係数にもつ、\(X\) の \(N\) 次式」であり、第2項第3項は「\(x\) の高々 \(1\) 次式を係数にもつ、\(X\) の\(1\) 次式」であることから、これは \(O(N^2)\) で計算できることが確かめられます。これを \(O(N)\) 回行うので全体では \(O(N^3)\) になります。

実装例(C++)