J1 实践-7 数字魔方大师

题目描述

在魔方世界锦标赛上，一项特殊的挑战吸引了所有选手的目光。这是一种全新的魔方，每个面不仅标注着数字 ($0$、$1$、 $2$)，还刻着神秘的字母 (M、E、X)。官方宣布只有找到正确的 MEX 组合，才能解开魔方的奥秘。

现在，裁判给出了一串长度为 $N$ 的数字序列 $A$ 和对应的字母序列 $S$。你需要：

$1$、找出所有满足条件的三元组 $(i,j,k)$，使得对应位置的字母正好构成 MEX $2$、 计算每组位置对应数字的 $mex$ 值 $3$、 最终求出所有 $mex$ 值之和

其中，$mex$ 值定义为：在一个数列中未出现的最小非负整数。 例如：

• $mex(0,1,2) = 3$
• $mex(1,1,2) = 0$
• $mex(0,2,2) = 1$

输入格式

共 $3$ 行： 第一行一个整数 $N$，表示 $A$ 序列的长度； 第二行 $N$ 个值为 $0,1,2$ 的整数，表示 $A$ 序列； 第三行一个长为 $N$ 的字符串，仅包含字符 MEX。

输出格式

一个整数，表示所有满足条件的三元组的 $mex$ 值之和。

样例输入

4
1 1 0 2
MEEX

样例输出

3

样例分析

使 $S_iS_jS_k$ = MEX 的三元组 $i,j,k\ (1\ \leq\ i\ <\ j\ <\ k\ \leq\ N)$ 有以下两个： $(i,j,k)=(1,2,4),(1,3,4)$。

由于 $\text{mex}(A_1,A_2,A_4)=\text{mex}(1,1,2)=0,\text{mex}(A_1,A_3,A_4)=\text{mex}(1,0,2)=3$，答案为 $0+3=3$。

数据范围

对于$100\%$ 的数据：$3\leq\ N\ \leq\ 2\times\ 10^5$，$N$ 为整数，$A_i\ \in\ \lbrace\ 0,1,2\rbrace$， $S$ 为长度为 $N$ 且仅包含字符 MEX 的字符串。