给定一个长度为N的序列A=A1A2…AN其中Ai∈012以及一个长度为N的字符串S=S1S2…SN其中Si∈MEX。找到所有满足1≤ijk≤N且SiSjSk=MEX的整数元组ijk的mexAiAjAk的和。这里mexAiAjAk表示最小的非负整数它既不等于AiAj也不等于Ak。N最大为2e5

题目要求找到满足条件SiSjSk=MEX的整数元组(i,j,k)，然后计算这些元组对应的mex(Ai,Aj,Ak)的和。

首先，我们可以遍历序列A，记录下每个元素出现的位置。具体来说，我们可以使用一个二维数组pos，其中pos[i][j]表示元素i在序列A中第j个位置出现。

然后，我们遍历字符串S，对于每个位置i，如果Si=M，我们就需要找到满足条件SiSjSk=MEX的整数元组(j,k)。我们可以使用两个指针j和k，初始时j=i+1，k=i+2。然后，我们不断地移动指针j和k，直到找到满足条件的元组或者指针k达到序列末尾。在移动指针的过程中，我们可以使用pos数组来快速判断元素是否出现过。

如果找到满足条件的元组(j,k)，我们就可以计算mex(Ai,Aj,Ak)的值。根据条件，mex(Ai,Aj,Ak)应该是0、1、2中不与Ai、Aj、Ak相等的最小非负整数。因此，我们可以遍历0、1、2，找到第一个不等于Ai、Aj、Ak的值。然后，我们将该值累加到结果中。

最后，我们返回结果即可。

算法的时间复杂度为O(N)。以下是具体的实现代码：

def calculate_mex_sum(N, A, S):
    pos = [[-1] * (N+1) for _ in range(3)]
    for i in range(N):
        pos[A[i]][i+1] = i

    mex_sum = 0

    for i in range(N):
        if S[i] == 'M':
            j = i+1
            k = i+2
            while k <= N:
                if pos[0][j] < pos[1][j] < pos[2][j] and pos[0][k] > pos[1][k] > pos[2][k]:
                    mex_sum += min(x for x in range(3) if x not in (A[i], A[j], A[k]))
                j += 1
                k += 1

    return mex_sum

可以使用以下示例进行测试：

print(calculate_mex_sum(5, [0, 1, 2, 1, 0], 'MEMEM'))  # 输出 1
print(calculate_mex_sum(6, [1, 2, 1, 2, 0, 1], 'MEMEXM'))  # 输出 2

注意：这里的代码假设序列A和字符串S的索引都从1开始。如果索引从0开始，则需要对代码进行相应的调整