Unstable String

题意翻译

$t$ 组询问，每次给定一个仅包含字符 `1` 或 `0` 或 `?` 字符串 $s$。定义一个子串是**不稳定的**当且仅当子串中任意相邻两数均不相同，如 $101010\cdots$ 或 $010101\cdots$。 我们称一个子串是**好看的**当且仅当我们可以将其中的 `?` 换为 `1` 或 `0` 其中一种使得这个子串是**不稳定的**。 求字符串中**好看的**子串个数之和。 $1\leq t\leq 10^4$，$1 \leq\left\vert s\right\vert\leq2\times10^5$，$\sum \left\vert s\right\vert\leq2\times10^5$。 translated by LinkZelda

题目描述

You are given a string $ s $ consisting of the characters 0, 1, and ?. Let's call a string unstable if it consists of the characters 0 and 1 and any two adjacent characters are different (i. e. it has the form 010101... or 101010...). Let's call a string beautiful if it consists of the characters 0, 1, and ?, and you can replace the characters ? to 0 or 1 (for each character, the choice is independent), so that the string becomes unstable. For example, the strings 0??10, 0, and ??? are beautiful, and the strings 00 and ?1??1 are not. Calculate the number of beautiful contiguous substrings of the string $ s $ .

输入输出格式

输入格式

The first line contains a single integer $ t $ ( $ 1 \le t \le 10^4 $ ) — number of test cases. The first and only line of each test case contains the string $ s $ ( $ 1 \le |s| \le 2 \cdot 10^5 $ ) consisting of characters 0, 1, and ?. It is guaranteed that the sum of the string lengths over all test cases does not exceed $ 2 \cdot 10^5 $ .

输出格式

For each test case, output a single integer — the number of beautiful substrings of the string $ s $ .

输入输出样例

输入样例 #1

3
0?10
???
?10??1100

输出样例 #1

8
6
25