CF1168B Good Triple

Toad Rash 有一个二进制字符串 $s$。二进制字符串只包含 $0$ 和 $1$。 设 $n$ 为 $s$ 的长度。 Rash 需要找出满足以下条件的整数对 $(l, r)$ 的数量：$1 \leq l \leq r \leq n$，并且存在至少一组整数 $x, k$，使得 $1 \leq x, k \leq n$，$l \leq x < x + 2k \leq r$，且 $s_x = s_{x+k} = s_{x+2k}$。 请你帮 Rash 计算满足条件的 $(l, r)$ 对的数量。

第一行输入字符串 $s$（$1 \leq |s| \leq 300\,000$），只包含 $0$ 和 $1$。

输出一个整数，表示满足条件的整数对 $(l, r)$ 的数量。即有多少对 $1 \leq l \leq r \leq n$，存在至少一组 $x, k$，使得 $1 \leq x, k \leq n$，$l \leq x < x + 2k \leq r$，且 $s_x = s_{x+k} = s_{x+2k}$。

在第一个样例中，需要计数的 $(l, r)$ 对有三组：$(1, 6)$、$(2, 6)$ 和 $(1, 5)$。 在第二个样例中，原始字符串不存在满足条件的 $x, k$，因此答案为 $0$。 由 ChatGPT 4.1 翻译