← 返回题目列表

AtCoder · abc441_e

H. A > B 子串

中文机器翻译题面 查看原题

分数: 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 个字符 S
  • AC:第 1 到第 2 个字符 S
  • CA:第 5 到 6 个字符 S
  • CABCA: 第 5 到第 9 个字符 S
  • A: 第 6 到 6 个字符 S
  • ABCA: 第 6 到第 9 个字符 S
  • CA: 第 8 到 9 个字符 S
  • A: 第 9 到 9 个字符 S

所有其他子字符串都不满足条件,因此打印 8.

请注意 A 和 CA 可以从多个位置获取,但如果从不同位置获取则单独计数。


示例输入 2

4
CCBC

示例输出 2

0

可能没有满足条件的子字符串。


示例输入 3

36
CABACBBBBBAABABACCBCABCCABAABABBCBAC

示例输出 3

136