多少个子串 A 比 B 多

ID: 16767

传统题

2000ms

1024MiB

显示难度普及+/提高−

上传者:

题目描述

给你一个长度为 $N$ 的字符串 $S$ ，仅由三种字符组成：'A'、'B' 和 'C'。

显然在 $S$ 中有 $\frac{N(N+1)}{2}$ 个非空连续子串。求其中有多少个子串满足“字符 'A' 的数量多于字符 'B' 的数量。

请注意，如果两个子串在 $S$ 中的不同位置，即使它们作为字符串相等，也要分别计算。

第一行一个数 $N$ 。

第二行字符串 $S$ 。

一行 $n$ 个数，为 $1 \sim n$ 。

10
ACBBCABCAB

对于 $100\%$ 的数据， $1 \le n \le 5\times 10^5$ 。