Bulb Queries

질의 구간을 $[l,r]$라고 하자. 켜져 있는 전구의 각 덩어리는 정확히 하나의 왼쪽 끝을 가진다. 따라서 덩어리의 개수는 덩어리의 왼쪽 끝인 위치의 개수와 같다.

$i \in [l,r]$에 대해, $i$번째 전구가 덩어리의 왼쪽 끝이면 $1$, 아니면 $0$인 확률변수 $X_i$를 정의하자.

구간의 첫 위치에서는 왼쪽 전구를 고려하지 않으므로

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

이다. $i>l$에서는 $i$번째 전구가 켜지고 $i-1$번째 전구가 꺼져야 하므로, 독립성에 의해

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

이다.

기댓값의 선형성에 의해 답은

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

이다.

$2 \le i \le N$에 대해

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

를 미리 계산하고, $S_i=\sum_{j=2}^{i}A_j$인 누적 합을 만들면 각 질의의 답은

$$P_l+S_r-S_l$$

로 $O(1)$에 계산할 수 있다.

전처리에는 $O(N)$, 모든 질의 처리에는 $O(Q)$ 시간이 들며, 메모리 사용량은 $O(N)$이다.

입력 확률은 소수점 아래 최대 두 자리이므로, 각 확률을 $0$부터 $100$까지의 정수로 바꾸어 계산하면 모든 중간값을 정수로 정확히 저장할 수 있다. 또는 충분한 정밀도의 double을 사용할 수 있다. 최댓값은 약 $25\ 000$이 될 수 있으므로 float은 사용하지 않는 것이 안전하다.

Solution written by GPT5.6