Let \(t_i(1\le i\le n)\) be the expected number of times so that the \(i\)-th square is painted black. Our task is to find \(E[\max\{t_i|i=1,2,\cdots,n\}]\)。

Note that

\[ \max(S)=\sum_{T\subseteq S,T\neq \varnothing}(-1)^{|T|-1}\min(T) \]

Proof: let \(S=\{s_0,s_1,\cdots,s_{k-1}\}\) where \(s_i\ge s_{i+1}\) holds for \(i=0,1,\cdots,k-2\), then

\[ \begin{aligned} \max(S)&=\sum_{i=0}^{k-1}[i=0]s_i=\sum_{i=0}^{k-1}s_i\sum_{j=0}^i(-1)^j\binom{i}{j}\\&=\sum_{i=0}^{k-1}s_i\sum_{T\subseteq \{0,1,\cdots,i-1\}}(-1)^{|T|}=\sum_{T}(-1)^{|T|-1}\min(T) \end{aligned} \]

Due to the linearity of expectation, we have

\[ E[\max\{t_i|i=1,2,\cdots,n\}]=\sum_{S\subseteq \{1,2,\cdots,n\}}(-1)^{|S|-1}E[\min\{t_i|i\in S\}] \]

If there are \(x\) intervals \([L_i,R_i]\) such that \([L_i,R_i]\cap S\neq \varnothing\), then \(E[\min\{t_i|i\in S\}]=\frac{m}{x}\). Let \(f(S)\) be such value \(x\) for a set \(S\).

Let \(\text{dp}(i,j)=\sum_{f(S)=j,S\subseteq\{1,2,\cdots,i\},i\in S}(-1)^{|S|-1}\), then it’s easy to calculate \(\text{dp}\) in \(O(N^2M)\) time. The answer is \(\sum_{i=1}^n\sum_{j=1}^{m}\text{dp}(i,j)\frac{m}{j}\).

By using some data structures like segment tree we can find \(\text{dp}\) values in \(O(NM\log N)\) time.

\(O(N^2M)\) Code: https://atcoder.jp/contests/abc242/submissions/41285151