题目链接： Link
本题解主要思路来源 @Rikka__(疯狂 % )。
考虑题里面的贡献的计算其实是一个连分数的倒数，即：
\[a_1+\frac {1}{a_2+\frac{1}{a_3 + ...}} \]若从 \(a_k\) 到 \(a_1\) 从下向上合并的话能够发现其实是一个 $ \Large \frac{a'}{b'} = \frac {1}{a_i+\frac{a}{b}}$ 的形式。（首先根据辗转相除法的那一套理论明显是不用考虑约分）
那么考虑将 \(a_i\) 合并上后对答案的影响：
\[\frac {a'}{b'} = \frac{1}{a_i+\frac{a}{b}} = \frac {b}{a_i \times b + a} \]那么也就是 \(a' = b ,b' = a_i \times b + a\)
转移是固定的故可以考虑使用矩阵进行转移：
\[\left[ \begin {array}{l} a'\\ b' \end{array} \right] = \left[ \begin {array}{l} 0 &1\\ 1&a_i \end{array} \right] \left[ \begin {array}{l} a\\ b \end{array} \right] \]故答案即为：
\[\left[ \begin {array}{l} 0&1\\ 1&a_1 \end{array} \right] \left[ \begin {array}{l} 0&1\\ 1&a_2 \end{array} \right] ... \left[ \begin {array}{l} 0&1\\ 1&a_k \end{array} \right] \left[ \begin {array}{l} 0\\ 1 \end{array} \right] \]继续考虑使用矩阵表述操作 W 和 E：
W：
\(a_k \rightarrow a_{k}+1\)
发现矩阵从 \(\left[\begin {array}{l}0&1\\1&a_k\end{array}\right]\) 变成 \(\left[\begin{array}{l} 0&1\\1&a_{k}+1 \end{array} \right ]\) 可以发现转移矩阵即为：\(\left[\begin{array}{l} 1&1\\0&1\end{array}\right]\) （右乘）
E：
\(a_k>1\)
\(a_k \rightarrow a_k - 1\) 并添加两个 \(1\) 到末尾。
按照上面的思路，发现 \(a_k \rightarrow a_k - 1\) 转移矩阵即为 \(\left[\begin{array}{l} 1&-1\\0&1\end{array}\right]\)
末尾添加两个 \(1\) 转移矩阵为 \(\left[\begin{array}{l}0&1\\1&1\end{array}\right]\left[\begin{array}{l}0&1\\1&1\end{array}\right]\)
按顺序整合一下即为 \(\left[\begin{array}{l}0&-1\\1&2\end{array}\right]\)
\(a_k = 1\)
这时 \(a_k\) 对应的矩阵为 \(\left[\begin{array}{l}0&1\\1&1\end{array}\right]\)。
按照正常的运算应该为 \(\left[\begin{array}{l}0&1\\1&a_{k-1}\end{array}\right]\left[\begin{array}{l}1&1\\0&1\end{array}\right]\left[\begin{array}{l}0&1\\1&1\end{array}\right]\) 。
按照结合律可变为 \(\left[\begin{array}{l}0&1\\1&a_{k-1}\end{array}\right]\left[\begin{array}{l}1&2\\1&1\end{array}\right]\)
我们同样设一个矩阵 \(\left[\begin{array}{l}x&y\\z&k\end{array}\right]\)
满足：
\[\left[\begin{array}{l}0&1\\1&a_{k-1}\end{array}\right]\left[\begin{array}{l}0&1\\1&1\end{array}\right]\left[\begin{array}{l}x&y\\z&k\end{array}\right] = \left[\begin{array}{l}0&1\\1&a_{k-1}\end{array}\right]\left[\begin{array}{l}1&2\\1&1\end{array}\right] \]解得矩阵 \(\left[\begin{array}{l}0&-1\\1&2\end{array}\right]\)
故对于 E 操作只需要乘上 \(\left[\begin{array}{l}0&-1\\1&2\end{array}\right]\)
剩余部分比较简单，只需要用一颗支持序列翻转、取反操作的平衡树实现即可。具体维护 区间连乘积，区间取反连乘积，区间翻转连乘积，区间取反翻转连乘积。同时维护取反标记和翻转标记即可
时间复杂度：\(O(n\log n)\)
优化：
其实有时空复杂度都更优的写法，考虑对于 REVERSE 和 FLIP 操作也像 W E 那样去通过矩阵进行转移，具体的通过矩阵中 \(4\) 个元素的线性组合去构造转移矩阵。
设矩阵 $A = \left[\begin{array}{l} a&b \ c&d \end{array}\right] $。
有：
\[Flip(A) =\left[\begin{array}{l} a-b&-b \\ -a+b-c+d&b+d \end{array}\right]\\ \space \\\space \\ Reverse(A) = \left[\begin{array}{l} d-2c&-2a+b-4c+2d \\ c&a+2c \end{array}\right] \]这样就可以不去维护 \(4\) 种乘积，空间和时间得到巨大优化。可以通过解方程来证明。
//editor : DRYAYST
//Wo shi ge da SHA BI
#include<bits/stdc++.h>
#define g() getchar()
#define il inline
#define ull unsigned long long
#define eps 1e-10
#define ll long long
#define pa pair<int, int>
#define for_1(i, n) for(int i = 1; i <= (n); ++i)
#define for_0(i, n) for(int i = 0; i < (n); ++i)
#define for_xy(i, x, y) for(int i = (x); i <= (y); ++i)
#define for_yx(i, y, x) for(int i = (y); i >= (x); --i)
#define for_edge(i, x) for(int i = head[x]; i; i = nxt[i])
#define int long long
#define DB double
#define ls tr[x].l
#define rs tr[x].r
#define m_p make_pair
#define fi first
#define se second
using namespace std;
const int N = 1e6 + 10, INF = 0x7f7f7f7f, mod = 998244353;
il int qpow(int x, int k) {int ans = 1; while(k) {if(k & 1) ans = ans * x % mod; x = x * x % mod; k >>= 1; } return ans; }
il int Add(int x, int y) {return (x += y) %= mod;}
il int Del(int x, int y) {return (x = x - y + mod) % mod;}
il int Mul(int x, int y) {return x * y % mod;}
il int inv(int x) {return qpow(x, mod - 2); }
inline int re() {
int x = 0, p = 1;
char ch = getchar();
while(ch > '9' || ch < '0') {if(ch == '-') p = -1; ch = getchar();}
while(ch <= '9' and ch >= '0') {x = (x << 3) + (x << 1) + (ch ^ 48); ch = getchar();}
return x * p;
}
mt19937 rd(20050426);
int n, Q, rt, cnt ;
char s[N], op[100];
struct Matrix {
int a[2][2]; Matrix() {memset(a, 0, sizeof(a)); }
il Matrix operator * (const Matrix &b) const {Matrix c; for_0(k, 2) for_0(i, 2) for_0(j, 2) c.a[i][j] = (c.a[i][j] + a[i][k] * b.a[k][j] % mod) % mod; return c;}
il Matrix Rev(Matrix A) {Matrix c;
c.a[0][0] = (A.a[1][1] - 2 * A.a[1][0] % mod + mod) % mod; c.a[0][1] = ((-2 * A.a[0][0] + A.a[0][1] - 4 * A.a[1][0] + 2 * A.a[1][1]) % mod + mod) % mod;
c.a[1][0] = A.a[1][0]; c.a[1][1] = (A.a[0][0] + 2 * A.a[1][0] % mod) % mod; return c;
}
il Matrix Flip(Matrix A) { Matrix c;
c.a[0][0] = (A.a[0][0] - A.a[0][1] + mod) % mod; c.a[0][1] = (-A.a[0][1] + mod) % mod;
c.a[1][0] = ((-A.a[0][0] + A.a[0][1] - A.a[1][0] + A.a[1][1]) % mod + mod) % mod; c.a[1][1] = (A.a[0][1] + A.a[1][1]) % mod; return c;
}
}A, B, ans, use; //A，B分别为两个转移矩阵
struct Tree {int l, r; int val, siz, rtag, ftag; Matrix V, S; }tr[N];
il int Newed(int x) { int id = ++cnt; tr[id].V = (x==0?A:B); tr[id].S = tr[id].V; tr[id].l = tr[id].r = 0; tr[id].siz = 1; tr[id].rtag = tr[id].ftag = 0; tr[id].val = rd(); return id; }
il void push_up(int x) {if(!x) return; tr[x].siz = tr[ls].siz + tr[rs].siz + 1; tr[x].S = tr[ls].S * tr[x].V * tr[rs].S; return; }
il void push_rdown(int x) { if(!x) return ; tr[x].S = use.Rev(tr[x].S); swap(tr[x].l, tr[x].r); tr[x].rtag ^= 1; }
il void push_fdown(int x) { if(!x) return ; tr[x].S = use.Flip(tr[x].S), tr[x].V = use.Flip(tr[x].V); tr[x].ftag ^= 1; }
il void push_down(int x) { if(!x) return; if(tr[x].rtag) push_rdown(tr[x].l), push_rdown(tr[x].r), tr[x].rtag = 0; if(tr[x].ftag) push_fdown(tr[x].l), push_fdown(tr[x].r), tr[x].ftag = 0; }
il int Merge(int k1, int k2) {
if(!k1 || !k2) return k1 + k2;
if(tr[k1].val < tr[k2].val) { push_down(k1); tr[k1].r = Merge(tr[k1].r, k2); push_up(k1); return k1; }
else {push_down(k2); tr[k2].l = Merge(k1, tr[k2].l); push_up(k2); return k2; }
}
int Build(int l, int r) {
if(l == r) {int now = Newed(s[l] != 'W'); return now;} int mid = (l + r) >> 1;
int k1 = Build(l, mid), k2 = Build(mid + 1, r); return Merge(k1, k2);
}
il int Insert(int rt, int fl) {return Merge(rt, Newed(fl)); }
void Split(int rt, int x, int &k1, int &k2) {
if(!rt) {k1 = 0; k2 = 0; return ; } push_down(rt);
if(tr[tr[rt].l].siz < x) {k1 = rt; Split(tr[rt].r, x - tr[tr[rt].l].siz -1 , tr[k1].r, k2); push_up(k1); }
else {k2 = rt; Split(tr[rt].l, x, k1, tr[k2].l); push_up(k2);}
}
il int Flip(int rt, int l, int r) { int k1, k2, k3; Split(rt, r, k1, k3); Split(k1, l - 1, k1, k2); push_fdown(k2); return Merge(k1, Merge(k2, k3)); }
il int Reverse(int rt, int l, int r) { int k1, k2, k3; Split(rt, r, k1, k3); Split(k1, l-1, k1, k2); push_rdown(k2); return Merge(k1, Merge(k2, k3)); }
signed main() {
n = re(), Q = re(); scanf("%s", s + 1); A.a[0][0] = 1; A.a[0][1] = 1; A.a[1][1] = 1; B.a[0][1] = mod - 1; B.a[1][0] = 1; B.a[1][1] = 2;
tr[0].V.a[0][0] = 1; tr[0].V.a[1][1] = 1; tr[0].S = tr[0].V; rt = Build(1, n); ans = A * tr[rt].S;
printf("%lld %lld\n", ans.a[1][1], ans.a[0][1]);
while(Q--) {
scanf("%s", op + 1);
if(op[1] == 'A') { scanf("%s", op + 1); rt = Insert(rt, op[1] != 'W'); }
else if(op[1] == 'F') {int l = re(), r = re(); rt = Flip(rt, l, r); }
else {int l = re(), r = re(); rt = Reverse(rt, l, r); }
ans = A * tr[rt].S; printf("%lld %lld\n", ans.a[1][1], ans.a[0][1]);
}
}
可能代码有点不能看,建议 loj 格式化后观看更清晰。