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

以下是一个时间复杂度为O(nlogn)的C++实现：

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>

using namespace std;

int main() {
    int n;
    cin >> n;

    vector<int> A(n);
    string S;
    cin >> S;

    for (int i = 0; i < n; i++) {
        cin >> A[i];
    }

    map<int, int> count;
    long long ans = 0;
    int zeros = 0, ones = 0, twos = 0;

    for (int k = n - 1; k >= 0; k--) {
        if (S[k] == 'X') {
            continue;
        }

        if (S[k] == 'M') {
            ans += zeros;
            ans += count[1];
            ans += count[2];
        }

        if (S[k] == 'E') {
            count[A[k]]++;
        }

        if (A[k] == 0) {
            zeros++;
        } else if (A[k] == 1) {
            ones++;
        } else {
            twos++;
        }
    }

    cout << ans << endl;

    return 0;
}

该实现使用了一个map来记录出现的元素个数。遍历字符串S和序列A时，根据不同的情况更新map和计算ans的值。最后输出ans即可