Смотритель зоопарка покупает коробку фруктов чтобы накормить своего любимца кролика. Фрукты в коробке — это последовательность яблок и апельсинов, которая представляется бинарной строкой $$$s_1s_2\ldots s_n$$$ длины $$$n$$$. В ней $$$1$$$ обозначает яблоко, а $$$0$$$ обозначает апельсин.
Поскольку у кролика аллергия на апельсины, смотритель зоопарка хочет найти наидлиннейшую подряд идующую подпоследовательность яблок. Пусть $$$f(l,r)$$$ — это наибольшая длина подряд идущей подпоследовательности яблок в подстроке $$$s_{l}s_{l+1}\ldots s_{r}$$$.
Помогите смотрителю зоопарка найти $$$\sum_{l=1}^{n} \sum_{r=l}^{n} f(l,r)$$$. Другими словами, найдите сумму $$$f$$$ по всем подстрокам.
В первой строке находится единственное целое число $$$n$$$ $$$(1 \leq n \leq 5 \cdot 10^5)$$$.
В следующей строке находится бинарная строка $$$s$$$ длины $$$n$$$ $$$(s_i \in \{0,1\})$$$.
Выведите единственное целое число: $$$\sum_{l=1}^{n} \sum_{r=l}^{n} f(l,r)$$$.
4 0110
12
7 1101001
30
12 011100011100
156
В первом тесте всего есть десять подстрок. Список этих подстрок (мы обозначаем $$$[l,r]$$$ как подстроку $$$s_l s_{l+1} \ldots s_r$$$):
Длины наибольших подряд идущих подпоследовательностей из единиц в этих подстроках $$$0,1,2,2,1,2,2,1,1,0$$$ соответственно. Поэтому ответ $$$0+1+2+2+1+2+2+1+1+0 = 12$$$.
Название |
---|