CF1535C Unstable String

给定一个由字符 $0$、$1$ 和 $?$ 组成的字符串 $s$。 我们称一个字符串为“不稳定的”，如果它只包含字符 $0$ 和 $1$，并且任意两个相邻字符都不同（即形如 $010101\ldots$ 或 $101010\ldots$）。 我们称一个字符串为“美丽的”，如果它只包含字符 $0$、$1$ 和 $?$，并且你可以将每个 $?$ 独立地替换为 $0$ 或 $1$，使得整个字符串变为不稳定的。 例如，字符串 $0??10$、$0$ 和 $???$ 是美丽的，而 $00$ 和 $?1??1$ 不是。 请计算字符串 $s$ 的美丽连续子串的数量。

第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。 每个测试用例的第一行包含一个字符串 $s$（$1 \le |s| \le 2 \cdot 10^5$），仅由字符 $0$、$1$ 和 $?$ 组成。 保证所有测试用例中字符串长度之和不超过 $2 \cdot 10^5$。

对于每个测试用例，输出一个整数，表示字符串 $s$ 的美丽子串数量。

由 ChatGPT 4.1 翻译