CF1428F.Fruit Sequences

Zookeeper is buying a carton of fruit to feed his pet wabbit. The fruits are a sequence of apples and oranges, which is represented by a binary string $s_1s_2\ldots s_n$ of length $n$. $1$ represents an apple and $0$ represents an orange.

Since wabbit is allergic to eating oranges, Zookeeper would like to find the longest contiguous sequence of apples. Let $f(l,r)$ be the longest contiguous sequence of apples in the substring $s_{l}s_{l+1}\ldots s_{r}$.

Help Zookeeper find $\sum_{l=1}^{n} \sum_{r=l}^{n} f(l,r)$, or the sum of $f$ across all substrings.

动物园管理员Zookeeper正在购买一盒水果来喂养他的宠物兔子（wabbit）。这些水果是一串苹果和橙子，用一个长度为 $n$ 的二进制字符串 $s_1s_2\ldots s_n$ 表示：其中 $1$ 代表一个苹果，$0$ 代表一个橙子。

由于兔子对橙子过敏，Zookeeper希望找到最长的连续苹果序列。令 $f(l,r)$ 表示子串 $s_{l}s_{l+1}\ldots s_{r}$ 中最长的连续苹果序列的长度。

请帮助 Zookeeper 计算 $\sum_{l=1}^{n} \sum_{r=l}^{n} f(l,r)$，即对所有子串的 $f(l,r)$ 值求和。

The first line contains a single integer $n$ $(1 \leq n \leq 5 \cdot 10^5)$.

The next line contains a binary string $s$ of length $n$ $(s_i \in {0,1})$

第一行包含一个整数 $n$ $(1 \leq n \leq 5 \cdot 10^5)$。

下一行包含一个长度为 $n$ 的二进制字符串 $s$ $(s_i \in \{0,1\})$

Print a single integer: $\sum_{l=1}^{n} \sum_{r=l}^{n} f(l,r)$.

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

In the first test, there are ten substrings. The list of them (we let $[l,r]$ be the substring $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

The lengths of the longest contiguous sequence of ones in each of these ten substrings are $0,1,2,2,1,2,2,1,1,0$ respectively. Hence, the answer is $0+1+2+2+1+2+2+1+1+0 = 12$.

在第一个测试用例中，共有十个子串。它们的列表如下（我们用 $[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$。