思路：数学优化

一个最朴素的方法：枚举每个区间（ $C(n,2)$ 个），计算区间中极长段的个数。时间复杂度 $O(n^2)$ ， $n = 2 \times 10^5$ , $n^2 = 4 \times 10^{10} > 10^8$ , 超时。

考虑原串其中的某一个极长段对总体答案的贡献:

题目内容

小蓝有一个由 0 和 1 组成的序列。定义一个序列的“段数”为序列中极大连续相同元素的段个数。例如序列 0011 由 00 和 11 两段组成，其段数为 $2$ 。

请你计算该序列所有非空子段的段数之和。

序列的长度 $n$ 满足 $1 \le n \le 2 \times 10^5$ ，序列中的每个元素均为 0 或 1。

第一行包含一个整数 $n$ ，表示序列的长度。