P1365 WJMZBMR打osu! Easy

题目背景

原维护队列参见 P1903

某一天 WJMZBMR 在打 osu，~~但是他太弱了，有些地方完全靠运气:(~~。

我们来简化一下这个游戏的规则

有 $n (n \leq 3 \times 10^{5})$ 次点击要做，成功了就是 o，失败了就是 x，分数是按 combo 计算的，连续 $a$ 个 combo 就有 $a \times a$ 分，combo 就是极大的连续 o。

比如ooxxxxooooxxx，分数就是 $2 \times 2 + 4 \times 4 = 4 + 16 = 20$ 。

Sevenkplus 闲的慌就看他打了一盘，有些地方跟运气无关要么是 o 要么是 x，有些地方 o 或者 x 各有 $50 %$ 的可能性，用 ? 号来表示。

比如 oo?xx 就是一个可能的输入。那么 WJMZBMR 这场 osu 的期望得分是多少呢？

比如 oo?xx 的话，? 是 o 的话就是 oooxx（ $9$ ），是 x 的话就是 ooxxx（ $4$ ），期望自然就是 $(4 + 9) / 2 = 6.5$ 了。

第一行一个整数 $n$ （ $n \leq 3 \times 10^{5}$ ），表示点击的个数

接下来一个字符串，每个字符都是 o，x，? 中的一个

一行一个浮点数表示答案

四舍五入到小数点后 $4$ 位

如果害怕精度跪建议用 long double 或者 extended。

1
2

4
????

4.1250

我们记期望连续的 $o$ 个数为 $l$ ， $f (i)$ 表示以第 $i$ 个字符结尾的期望得分。

当当前字符为 o 时，

f (i) = f (i - 1) + [(l + 1)^{2} - l^{2}] = f (i - 1) + 2 \times l + 1, l = l + 1

当当前字符为 x 时，

f (i) = f (i - 1), l = 0

当当前字符为 ? 时，把以上两种转移乘以 $\frac{1}{2}$ 并相加即可，

f (i) = f (i - 1) + \frac{[(l + 1)^{2} - l^{2}] + 0}{2} = f (i - 1) + l + 0.5, l = \frac{l + 1}{2}