思路: 思维

考虑字符串中每个 tzzt 对答案的贡献。

下标从 $0$ 开始。假设是 s[i, i+3] = "tzzt"，那么这个 tzzt 对于答案的贡献为：所有 $l <= i, r >= i+3$ 的字符串。

这样的字符串一共有 $(l+1) \times (n-r)$ 个。

题目内容

对于一个仅由字符 t 和 z 构成的字符串，定义其“价值”为该字符串中目标模式 tzzt 作为连续子串出现的次数，重叠出现也计入。例如，tzzt 的价值为 1，tzztzzt 的价值为 2，tzzzt 的价值为 0。

现在给定一个仅由字符 t 和 z 构成的长度为 $n$ 的字符串，请计算它的所有连续子串的价值之和。

保证 $n \le 2 \times 10^5$ 。