核心思路

1.矩阵表示法

每个操作可以看作一个 $2\times 2$ 矩阵作用在向量 $(\text{分子}, \text{分母})$ 上：

W 操作：$a_k \to a_k + 1$ 对应矩阵：

E 操作（当最后一项 $=1$）：倒数第二项 $+1$ 对应矩阵（经过推导）：

2.操作序列的乘积

整个操作序列对应的矩阵乘积作用在初始向量 $(0, 1)$ 上，得到最终的有理数 $\frac{a}{b}$。

3.处理修改操作

需要支持：

APPEND：在序列末尾添加操作

FLIP：区间内 W↔E 互换

REVERSE：区间内操作逆序

使用 Treap 维护序列，每个节点存储：

该操作对应的矩阵 $val$（正向）

该操作取反后的矩阵 $ival$（W↔E）

区间乘积 $sum$（正向）

区间逆序乘积 $rev$

以及对应的取反版本 $inv$ 和 $invrev$

4.懒标记

invt：表示该子树是否需要 W↔E

revt：表示该子树是否需要逆序

算法步骤

初始化

定义 $M_W$ 和 $M_E$ 矩阵

建立 Treap 结构体，维护 6 个矩阵和懒标记

空节点的矩阵为单位矩阵

建树

读入初始操作序列，为每个操作创建节点

使用 Treap 的随机合并建树

查询

根节点的 $sum$ 矩阵就是整个序列的乘积

输出 $sum[0][0]$ 和 $sum[1][0]$ 作为分子分母（模 $998244353$）

修改操作

APPEND

创建新节点

合并到树末尾

FLIP l r

分裂出 $[l, r]$ 区间

对该区间打 invt 标记

合并回去

REVERSE l r

分裂出 $[l, r]$ 区间

对该区间打 revt 标记

合并回去

复杂度分析

预处理：$O(n)$ 建树

每次操作：$O(\log L)$，其中 $L$ 是当前序列长度

总复杂度：$O((n+q)\log L)$，可以处理 $2\times 10^5$ 的数据规模

总结

本题通过将操作转化为矩阵乘法，利用平衡树维护序列并支持区间翻转和取反操作，高效地解决了动态操作序列下的连分数计算问题。关键在于发现 W 和 E 操作的矩阵表示，以及设计合适的 Treap 节点结构来维护正反、取反等各种情况下的区间乘积。

AC代码

根据ac代码编写题解，注意排版
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5, mod = 998244353;
int n, q, idx, z, root;
struct matrix {
    int w[2][2] = {};
    matrix operator*(const matrix &b) {
        matrix res;
        res.w[0][0] = (1ll * w[0][0] * b.w[0][0] + 1ll * w[0][1] * b.w[1][0]) % mod;
        res.w[0][1] = (1ll * w[0][0] * b.w[0][1] + 1ll * w[0][1] * b.w[1][1]) % mod;
        res.w[1][0] = (1ll * w[1][0] * b.w[0][0] + 1ll * w[1][1] * b.w[1][0]) % mod;
        res.w[1][1] = (1ll * w[1][0] * b.w[0][1] + 1ll * w[1][1] * b.w[1][1]) % mod;
        return res;
    }
    void print() {
        printf("%d %d\n", w[0][0], w[1][0]);
    }
    void init() {
        w[0][0] = w[1][1] = 1, w[0][1] = w[1][0] = 0;
    }
} op1, op2;
int read() {
    int x = 0, f = 1;
    char ch = getchar();

    while (ch < '0' || ch > '9') {
        if (ch == '-')
            f = -1;

        ch = getchar();
    }

    while (ch >= '0' && ch <= '9') {
        x = x * 10 + ch - '0';
        ch = getchar();
    }

    return x * f;
}
struct treap {
    matrix val, sum, inv, rev, ival, invrev;
    int l, r, rnd, sz;
    bool invt, revt;
} s[N];
void pushup(int rt) {
    s[rt].sz = s[s[rt].l].sz + 1 + s[s[rt].r].sz;
    s[rt].sum = s[s[rt].l].sum * s[rt].val * s[s[rt].r].sum;
    s[rt].inv = s[s[rt].l].inv * s[rt].ival * s[s[rt].r].inv;
    s[rt].rev = s[s[rt].r].rev * s[rt].val * s[s[rt].l].rev;
    s[rt].invrev = s[s[rt].r].invrev * s[rt].ival * s[s[rt].l].invrev;
}
void change_rev(int rt) {
    if (!rt)
        return;

    s[rt].revt ^= 1;
    swap(s[rt].rev, s[rt].sum);
    swap(s[rt].invrev, s[rt].inv);
    swap(s[rt].l, s[rt].r);
}
void change_inv(int rt) {
    if (!rt)
        return;

    s[rt].invt ^= 1;
    swap(s[rt].val, s[rt].ival);
    swap(s[rt].sum, s[rt].inv);
    swap(s[rt].rev, s[rt].invrev);
}
void pushdown(int rt) {
    if (!rt)
        return;

    if (s[rt].invt) {
        change_inv(s[rt].l);
        change_inv(s[rt].r);
        s[rt].invt = 0;
    }

    if (s[rt].revt) {
        change_rev(s[rt].l);
        change_rev(s[rt].r);
        s[rt].revt = 0;
    }
}
void split(int u, int v, int &x, int &y) {
    if (!u)
        return x = y = 0, void();

    pushdown(u);

    if (s[s[u].l].sz + 1 <= v) {
        x = u;
        split(s[u].r, v - s[s[u].l].sz - 1, s[x].r, y);
        pushup(x);
    } else {
        y = u;
        split(s[u].l, v, x, s[y].l);
        pushup(y);
    }
}
int merge(int x, int y) {
    if (!x || !y)
        return x + y;

    if (s[x].rnd < s[y].rnd) {
        pushdown(x);
        s[x].r = merge(s[x].r, y);
        pushup(x);
        return x;
    } else {
        pushdown(y);
        s[y].l = merge(x, s[y].l);
        pushup(y);
        return y;
    }
}
void newnode(int &rt, matrix val, matrix ival) {
    rt = ++idx;
    s[rt].sz = 1;
    s[rt].sum = s[rt].val = s[rt].rev = val;
    s[rt].ival = s[rt].inv = s[rt].invrev = ival;
    s[rt].rnd = rand();
}
int main() {
    //freopen("code.in", "r", stdin);
    //freopen("code.out", "w", stdout);
    s[0].inv.init();
    s[0].invrev.init();
    s[0].ival.init();
    s[0].rev.init();
    s[0].sum.init();
    s[0].val.init();

    n = read(), q = read();
    op1.w[0][0] = op1.w[1][0] = op1.w[1][1] = 1;
    op2.w[0][0] = 2, op2.w[0][1] = 1, op2.w[1][0] = mod - 1;
    newnode(z, op1, op1);
    root = z;

    for (int i = 1; i <= n; i++) {
        char w;
        cin >> w;

        if (w == 'W')
            newnode(z, op1, op2), root = merge(root, z);
        else
            newnode(z, op2, op1), root = merge(root, z);
    }

    s[root].sum.print();

    while (q--) {
        string s1;
        int l, r;
        cin >> s1;

        if (s1[0] == 'A') {
            cin >> s1;

            if (s1[0] == 'W')
                newnode(z, op1, op2), root = merge(root, z);
            else
                newnode(z, op2, op1), root = merge(root, z);
        } else if (s1[0] == 'F') {
            int l = read(), r = read();
            int x, y, z;
            split(root, r + 1, x, z);
            split(x, l, x, y);
            change_inv(y);
            root = merge(x, merge(y, z));
        } else {
            int l = read(), r = read();
            int x, y, z;
            split(root, r + 1, x, z);
            split(x, l, x, y);
            change_rev(y);
            root = merge(x, merge(y, z));
        }

        s[root].sum.print();
    }

    return 0;
}