CF1428F Fruit Sequences

动物管理员正在为他的宠物兔子购买一箱水果。这些水果是一串苹果和橙子的序列，用一个长度为 $n$ 的二进制字符串 $s_1s_2\ldots s_n$ 表示。$1$ 代表苹果，$0$ 代表橙子。 由于兔子对橙子过敏，动物管理员希望找到最长的连续苹果序列。设 $f(l,r)$ 表示子串 $s_l s_{l+1} \ldots s_r$ 中最长的连续苹果（即 $1$）的长度。 请你帮助动物管理员计算 $\sum_{l=1}^{n} \sum_{r=l}^{n} f(l,r)$，即所有子串的 $f$ 值之和。

第一行包含一个整数 $n$，$1 \leq n \leq 5 \cdot 10^5$。 第二行包含一个长度为 $n$ 的二进制字符串 $s$，其中 $s_i \in \{0,1\}$。

输出一个整数，表示 $\sum_{l=1}^{n} \sum_{r=l}^{n} f(l,r)$。

在第一个测试样例中，一共有十个子串。我们用 $[l,r]$ 表示子串 $s_l s_{l+1} \ldots s_r$： - $[1,1]$：0 - $[1,2]$：01 - $[1,3]$：011 - $[1,4]$：0110 - $[2,2]$：1 - $[2,3]$：11 - $[2,4]$：110 - $[3,3]$：1 - $[3,4]$：10 - $[4,4]$：0 每个子串中最长连续 $1$ 的长度分别为 $0,1,2,2,1,2,2,1,1,0$。因此，答案为 $0+1+2+2+1+2+2+1+1+0=12$。 由 ChatGPT 4.1 翻译