← 返回题目列表

AtCoder · awc0059_d

D. 均衡饮食

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

分数: 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