感觉难度和今年 D2T2 差不多。
首先一个很显然的事情是，每一步得到的分数的分子分母都是互质的，证明参考 SBT。而最后答案要求我们将分子分母都求出来而不是求分数值，所以可以很明显的想到将分数当成一个二元组然后维护变换。
考虑从右往左扫，假设当前分数为 \(\dfrac{x}{y}\)，那么扫过 \(a_k\) 这个元素之后就会变成，\(\begin{bmatrix}x&y\end{bmatrix}\times\begin{bmatrix}a_{k}&1\\1&0\end{bmatrix}\)，而初始情况为了满足 \(\begin{bmatrix}x&y\end{bmatrix}\times\begin{bmatrix}a_{k}&1\\1&0\end{bmatrix}=\begin{bmatrix}a_k&1\end{bmatrix}\)，所以初始情况应有 \(x=1,y=0\)，所以如果给的是序列 A 而不是 WE 序列，那么所求即为 \(\begin{bmatrix}a_{k}&1\\1&0\end{bmatrix}\begin{bmatrix}a_{k-1}&1\\1&0\end{bmatrix}\cdots\begin{bmatrix}a_{1}&1\\1&0\end{bmatrix}\)，使用线段树维护矩阵乘法即可。
接下来考虑怎么维护这个 WE 序列。先考虑 W，由于 \(\begin{bmatrix}1&1\\0&1\end{bmatrix}\begin{bmatrix}a_{k}&1\\1&0\end{bmatrix}=\begin{bmatrix}a_{k}+1&1\\1&0\end{bmatrix}\)，所以如果序列末尾有个 W，那么相当于在整个矩乘的式子左边添加一个 \(\begin{bmatrix}1&1\\0&1\end{bmatrix}\)。
其次考虑 E。考虑 E 的两种情况：
- 序列的最后一个元素为 \(1\)，由于 \(\begin{bmatrix}x&y\end{bmatrix}\times\begin{bmatrix}1&1\\1&0\end{bmatrix}\times \begin{bmatrix}1&1\\0&1\end{bmatrix}=\begin{bmatrix}x+y&2x+y\end{bmatrix}\)，且 \(\begin{bmatrix}x&y\end{bmatrix}\times\begin{bmatrix}2&-1\\1&0\end{bmatrix}\times\begin{bmatrix}1&1\\1&0\end{bmatrix}=\begin{bmatrix}x+y&2x+y\end{bmatrix}\)，所以这种情况相当于在序列左边添加一个 \(\begin{bmatrix}2&-1\\1&0\end{bmatrix}\)。
- 序列的最后一个元素不是 \(1\)，那么相当于在序列左边添加 \(\begin{bmatrix}1&1\\1&0\end{bmatrix}\times \begin{bmatrix}1&1\\1&0\end{bmatrix}\times \begin{bmatrix}-1&1\\1&0\end{bmatrix}\)，而我们刚好发现这个式子的结果也是 \(\begin{bmatrix}2&-1\\1&0\end{bmatrix}\)。
换句话说，如果序列末尾有个 E，那么相当于在整个矩乘的式子左边添加一个 \(\begin{bmatrix}2&-1\\1&0\end{bmatrix}\)。
这样问题就容易了：相当于把序列 reverse 过来，把 w 替换为 \(\begin{bmatrix}1&1\\0&1\end{bmatrix}\)，E 替换为 \(\begin{bmatrix}2&-1\\1&0\end{bmatrix}\)，求矩阵连乘后的结果。由于涉及 reverse 和 flip，使用平衡树维护即可。
const int MAXN=2e5;
const int MOD=998244353;
mt19937 rng(time(0));
int n,qu;char str[MAXN+5];
struct mat{
int a[2][2];
mat(){memset(a,0,sizeof(a));}
friend mat operator *(const mat &X,const mat &Y){
mat res;
for(int i=0;i<2;i++)for(int j=0;j<2;j++)for(int k=0;k<2;k++)
res.a[i][j]=(res.a[i][j]+1ll*X.a[i][k]*Y.a[k][j])%MOD;
return res;
}
}W,E,I;
struct node{int ch[2],key,typ,siz,rev_lz,flip_lz;mat v[2][2];}s[MAXN+5];
int rt,ncnt;
int nwnd(int x){
++ncnt;s[ncnt].key=rng();s[ncnt].typ=x;s[ncnt].siz=1;
s[ncnt].v[0][0]=s[ncnt].v[0][1]=(x)?E:W;
s[ncnt].v[1][0]=s[ncnt].v[1][1]=(x)?W:E;
return ncnt;
}
void pushup(int k){
s[k].v[0][0]=s[s[k].ch[0]].v[0][0]*((s[k].typ)?E:W)*s[s[k].ch[1]].v[0][0];
s[k].v[1][0]=s[s[k].ch[0]].v[1][0]*((s[k].typ)?W:E)*s[s[k].ch[1]].v[1][0];
s[k].v[0][1]=s[s[k].ch[1]].v[0][1]*((s[k].typ)?E:W)*s[s[k].ch[0]].v[0][1];
s[k].v[1][1]=s[s[k].ch[1]].v[1][1]*((s[k].typ)?W:E)*s[s[k].ch[0]].v[1][1];
s[k].siz=s[s[k].ch[0]].siz+s[s[k].ch[1]].siz+1;
}
void tag_rev(int k){
swap(s[k].ch[0],s[k].ch[1]);s[k].rev_lz^=1;
swap(s[k].v[0][0],s[k].v[0][1]);swap(s[k].v[1][0],s[k].v[1][1]);
}
void tag_flip(int k){
s[k].typ^=1;s[k].flip_lz^=1;
swap(s[k].v[0][0],s[k].v[1][0]);swap(s[k].v[0][1],s[k].v[1][1]);
}
void pushdown(int k){
if(s[k].rev_lz){
if(s[k].ch[0])tag_rev(s[k].ch[0]);
if(s[k].ch[1])tag_rev(s[k].ch[1]);
s[k].rev_lz=0;
}
if(s[k].flip_lz){
if(s[k].ch[0])tag_flip(s[k].ch[0]);
if(s[k].ch[1])tag_flip(s[k].ch[1]);
s[k].flip_lz=0;
}
}
int merge(int a,int b){
if(!a||!b)return a+b;pushdown(a);pushdown(b);
if(s[a].key<s[b].key)return s[a].ch[1]=merge(s[a].ch[1],b),pushup(a),a;
else return s[b].ch[0]=merge(a,s[b].ch[0]),pushup(b),b;
}
void split(int k,int sz,int &a,int &b){
if(!k)return a=b=0,void();pushdown(k);
if(sz<=s[s[k].ch[0]].siz)return b=k,split(s[k].ch[0],sz,a,s[k].ch[0]),pushup(k),void();
else return a=k,split(s[k].ch[1],sz-s[s[k].ch[0]].siz-1,s[k].ch[1],b),pushup(k),void();
}
void calc(){
int x=s[rt].v[0][0].a[0][0],y=s[rt].v[0][0].a[0][1];
printf("%d %d\n",x,(x+y)%MOD);
}
int main(){
scanf("%d%d%s",&n,&qu,str+1);
W.a[0][0]=1;W.a[0][1]=1;W.a[1][0]=0;W.a[1][1]=1;
E.a[0][0]=2;E.a[0][1]=MOD-1;E.a[1][0]=1;E.a[1][1]=0;
I.a[0][0]=I.a[1][1]=1;
for(int i=0;i<2;i++)for(int j=0;j<2;j++)s[0].v[i][j]=I;
for(int i=1;i<=n;i++)rt=merge(nwnd(str[i]=='E'),rt);
calc();
while(qu--){
static char opt[10];scanf("%s",opt+1);
if(opt[1]=='A'){
static char chr[10];scanf("%s",chr+1);
++n;rt=merge(nwnd(chr[1]=='E'),rt);
}else if(opt[1]=='F'){
int l,r,k1,k2,k3;scanf("%d%d",&l,&r);
swap(l,r);l=n-l+1;r=n-r+1;
split(rt,r,k1,k3);split(k1,l-1,k1,k2);tag_flip(k2);
rt=merge(merge(k1,k2),k3);
}else{
int l,r,k1,k2,k3;scanf("%d%d",&l,&r);
swap(l,r);l=n-l+1;r=n-r+1;
split(rt,r,k1,k3);split(k1,l-1,k1,k2);tag_rev(k2);
rt=merge(merge(k1,k2),k3);
}calc();
}
return 0;
}
/*
10 1
EEWEEWWWEE
FLIP 1 9
*/