分数: 400 分
问题陈述
高桥为了自己的健康,每天都在努力均衡地吃蔬菜和水果。总结完他的用餐记录后 N 天,他获得了一根字符串 S 长度 N。的 i- 第一个字符 S 代表当天的膳食内容 i,并且是以下之一:
V: 只吃蔬菜F: 只吃水果B: 蔬菜和水果都吃了N: 都没吃
的 蔬菜得分 v_i 和 水果分数 f_i 当天 i 根据膳食内容定义如下:
| 字符 | 菜分 v_i | 水果分数 f_i |
|---|---|---|
V |
1 | 0 |
F |
0 | 1 |
B |
1 | 1 |
N |
0 | 0 |
对于一对整数 (l, r) 满意 1 \leq l \leq r \leq N,如果蔬菜总分 \displaystyle\sum_{i=l}^{r} v_i 和水果总分 \displaystyle\sum_{i=l}^{r} f_i 从一天开始的时间间隔 l 到今天 r 相等,则该区间称为 平衡期。这包括两个总数均为 0.
查找对的数量 (l, r) 形成一个平衡时期。
约束
- 1 \leq N \leq 10^6
- S 是一个长度为 N,每个字符都是以下之一
V,F,B,N
输入
N S
- 第一行包含一个整数 N 代表天数。
- 第二行包含一个字符串 S 长度 N 代表用餐记录。
输出
在一行上打印平衡周期数。
示例输入 1
5 VFBNN
示例输出 1
10
示例输入 2
4 BNNF
示例输出 2
6
示例输入 3
12 VFBNVFBNVFBN
示例输出 3
48
示例输入 4
32 VVFFBBNNVVFFBBNNVVFFBBNNVVFFBBNN
示例输出 4
244
示例输入 5
1 N
示例输出 5
1