Bulb Queries

Consider a query interval $[l,r]$. Every contiguous group of bulbs that are on has exactly one left endpoint. Therefore, the number of groups equals the number of positions that are left endpoints of groups.

For each $i \in [l,r]$, define the indicator random variable $X_i$ to be $1$ if bulb $i$ is the left endpoint of a group and $0$ otherwise.

At the first position of the interval, the bulb to its left is ignored, so

$$\mathbb{E}[X_l]=P_l.$$

For $i>l$, bulb $i$ must be on and bulb $i-1$ must be off. By independence,

$$\mathbb{E}[X_i]=P_i(1-P_{i-1}).$$

By linearity of expectation, the answer is

$$P_l+\sum_{i=l+1}^{r} P_i(1-P_{i-1}).$$

For every $2 \le i \le N$, precompute

$$A_i=P_i(1-P_{i-1}),$$

and let $S_i=\sum_{j=2}^{i}A_j$. Then each query is answered in time as

$$P_l+S_r-S_l.$$

The preprocessing takes $O(N)$ time, all queries take $O(Q)$ time, and the memory usage is $O(N)$.

Because each input probability has at most two digits after the decimal point, it can be converted to an integer from $0$ to $100$. This makes every intermediate value exact. Using double is also sufficient, but float is unsafe because the maximum answer can be about $25\ 000$.

Solution written by GPT5.6