分数: 450 点
问题陈述
给你一个字符串 S 长度 N 由三种字符组成: A, B,和 C.
有 \dfrac{N(N+1)}2 的非空连续子串 S。找出其中有多少包含更多 A比 Bs。
请注意,如果两个子字符串取自不同的位置,则它们将被单独计数。 S,即使它们作为字符串相等。
什么是子串?
A 子字符串
长度为 $$$l$$$ 的字符串 $$$s_1s_2 \ldots s_l$$$ 的 of S 是从开头删除零个或多个字符,从结尾删除零个或多个字符得到的字符串 S.
例如, AB 是一个子串 ABC,但是 AC 不是以下的子串 ABC.
约束
- 1\le N\le5\times10 ^ 5
- S 是一个长度为 N 组成
A,B,和C. - N 是一个整数。
输入
输入由标准输入按以下格式给出:
N S
输出
打印连续子串的数量 S 包含更多 A比 Bs。
示例输入 1
10 ACBBCABCAB
示例输出 1
8
以下八个子串满足条件:
A:第 1 到第 1 个字符 SAC:第 1 到第 2 个字符 SCA:第 5 到 6 个字符 SCABCA: 第 5 到第 9 个字符 SA: 第 6 到 6 个字符 SABCA: 第 6 到第 9 个字符 SCA: 第 8 到 9 个字符 SA: 第 9 到 9 个字符 S
所有其他子字符串都不满足条件,因此打印 8.
请注意 A 和 CA 可以从多个位置获取,但如果从不同位置获取则单独计数。
示例输入 2
4 CCBC
示例输出 2
0
可能没有满足条件的子字符串。
示例输入 3
36 CABACBBBBBAABABACCBCABCCABAABABBCBAC
示例输出 3
136