CF2276E Good Substrings

给定一个长度为 $n$ 的字符串 $s$，仅由数字组成。 字符串 $s$ 的子串指的是其字符的连续子序列。对于任意子串 $s_{l\dots r}$，如果它包含字符串 $2025$ 作为子序列，且不包含字符串 $2026$ 作为子序列，则这个子串是坏的；否则，这个子串是好的。例如，字符串 $2025$、$72707275$、$20625$ 是坏的，但字符串 $20256$、$2026$、$777$、$1290723576$ 是好的。 对于每一个 $1$ 到 $n$ 的下标 $i$，请你计算包含该下标的好子串的个数。也就是说，对于每个 $i$，计算所有满足 $1 \leq l \leq i \leq r \leq n$ 且 $s_{l\dots r}$ 是好子串的整数对 $(l, r)$ 的数量。

第一行包含一个整数 $t$（$1 \leq t \leq 10^4$），表示测试用例的数量。 每个测试用例的第一行包含一个整数 $n$（$1 \leq n \leq 3 \cdot 10^5$）。 每个测试用例的第二行包含一个长度为 $n$ 的字符串 $s$，仅由数字组成。 输入有额外约束：所有测试用例中 $n$ 的总和不超过 $3 \cdot 10^5$。

对于每个测试用例，输出 $n$ 个整数，第 $i$ 个整数表示包含下标 $i$ 的好子串的数量。

由 ChatGPT 5 翻译