ABC 308E MEX

题意
给定长度为N的包含0,1,2的a序列，和一个长度为N的包含字符M,E,X的字符串s。对于所以符合条件的1<=i<j<k<=N，使得s[i]s[j]s[k]=="MEX"的三元组（i,j,k），请你求出所有mex(a[i],a[j],a[k])之和。mex()函数表示未出现在序列中的最小非负整数。

思路
我们先看一个非常典的题目，给你一串由a,b,c构成的字符串，请问里面能构成"abc"的子序列有多少组。这个题的思路就可以沿用于此题，我们维护一个a出现次数的前缀和，和一个c出现次数的后缀和，如果一旦遇到b这个字符，根据乘法原理，我们就用a的前缀和乘以c的后缀和，然后加到ans上去，就可以O(n)解决此题。同理，对于这个题，我们对于每个M与X，前者开三个前缀和、后者三个后缀和，表示字符为M，对应的数字是0,1,2；字符为X，对应的数字是0,1,2。然后O(n)遍历，一旦遇到了E，那么我们就对于9种情况全部操作一遍，然后算出贡献即可。

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=2e5+10;
int a[maxn];
int s[maxn]; 
int m[maxn][5];
int x[maxn][5];

signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	int n;
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i];
	string sss;
	cin>>sss;
	for(int i=1;i<=n;i++)
	{
		char flag=sss[i-1];
		if(flag=='M') s[i]=0;
		if(flag=='E') s[i]=1;
		if(flag=='X') s[i]=2;
	}
	for(int i=1;i<=n;i++)
	{
		m[i][0]=m[i-1][0];
		m[i][1]=m[i-1][1];
		m[i][2]=m[i-1][2];
		if(s[i]==0) m[i][a[i]]++;
	}
	for(int i=n;i>=1;i--)
	{
		x[i][0]=x[i+1][0];
		x[i][1]=x[i+1][1];
		x[i][2]=x[i+1][2];
		if(s[i]==2) x[i][a[i]]++;
	}
	int ans=0;
	for(int i=1;i<=n;i++)
	{
		if(s[i]==1)
		{
			for(int j=0;j<=2;j++)
			{
				for(int k=0;k<=2;k++)
				{
					int t=0;
					for(t=0;t<=3;t++)
						if(t!=a[i]&&t!=j&&t!=k) break;
					ans+=t*m[i][j]*x[i][k];
				}
			}
		}
	}
	cout<<ans<<endl;
	return 0;
 }