MEX

题目描述

给你一个长度为 $N$ 的序列 $A=(A_1,A_2,\dots,A_N)$，由 $0$、$1$ 和 $2$ 组成， 以及一个长度为 $N$ 的字符串 $S=S_1S_2\dots S_N$，由 $M$、$E$ 和 $X$ 组成。 求在所有满足 $1 \leq i < j < k \leq N$ 且 $S_iS_jS_k= MEX$ 的整数三元组 $(i,j,k)$ 上的 $\text{mex}(A_i,A_j,A_k)$ 之和。 这里，$\text{mex}(A_i,A_j,A_k)$ 表示既不等于 $A_i,A_j$ 也不等于 $A_k$ 的最小非负整数。

输入格式

输入按下述格式由标准输入给出： $N$ $A_1$ $A_2$ $\dots$ $A_N$ $S$

输出格式

输出一个整数，表示答案。

4
1 1 0 2
MEEX

3

3
0 0 0
XXX

0

15
1 1 2 0 0 2 0 2 0 0 0 0 0 2 2
EXMMXXXEMEXEXMM

13

提示

$3\leq N \leq 2\times 10^5$ $N$ 是一个整数。 $A_i \in \lbrace 0,1,2\rbrace$ $S$ 是一个长度为 $N$ 的字符串，由 $M$、$E$ 和 $X$ 组成。满足 $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$。

标签: AtCoder|abc308E

来源

AtCoder|abc308E