解説

まず、誰も入ろうとしていないスタジアムにおいて、求める確率は $1$ です。 また、各プレイヤー $i$ について、入ろうとしているスタジアムのうちスタジアム $k$ に入らない確率は独立に

• $k$ が $l_i,l_i+1,...,r_i$ に含まれているとき $\displaystyle \frac{r_i-l_i+1-1}{r_i-l_i+1} = \frac{r_i-l_i}{r_i-l_i+1}$
• 含まれていないとき $1$

であることから、各スタジアムにおける確率を管理する配列(初めは全て $1$)を $P$ として、各 $i$ について $[l_i,r_i+1)$ の範囲で $\frac{r_i-l_i}{r_i-l_i+1}$ を乗算すればよいことになります。

この操作は遅延セグメント木を利用することで操作1回当たり $O(logM)$ で可能であるため、全体としても $O((N+M)logM)$ で動作します。これは本制約下で十分高速です。よって、この問題を解くことができました。

追記

遅延セグメント木の代わりにimos法を用いても解くことができます。(累積積) こちらは $O(N+M)$ で動作し、さらに高速化が望めます。

具体的には、 最初配列を $a = (1,1,...,1)$ としておき、$a_{l_i}$ に $\frac{r_i-l_i}{r_i-l_i+1}$ を乗算し、$a_{r_i+1}$ に $\frac{r_i-l_i}{r_i-l_i+1}$ を除算するという操作を 各 $i(1 \leq i \leq N)$ について行い、最後にimos法の要領で各 $i$ ごとに $\prod_{j=1}^{i} j$ を求めその答えを出力すればよいです。

しかし、一つ問題が生じます。それは、 $l_i = r_i$ となる場合があることです。$l_i = r_i$ となる場合、$a_{l_i}$ に $0$ を乗算し、 $a_{r_i+1}$ に $0$ を除算することになってしまいます。そこで、0除算を回避するために、次のようにします。

• $l_i < r_i$ のとき、$a_{l_i}$ に $\frac{r_i-l_i}{r_i-l_i+1}$ を乗算し、$a_{r_i+1}$ に $\frac{r_i-l_i}{r_i-l_i+1}$ を除算する。
• $l_i = r_i$ のとき、$l_i$ の値を集合 $B$ に入れておく。
• 最後の計算の際、$i$ が $B$ に含まれているならば、答えの代わりに $0$ を出力する。

このようにすることで0除算を回避しつつ、正しく答えを出力できます。時間計算量は $O(N+M)$ です。