思路：分块 + 前缀

加O2优化AC，不加过11/21个数据

首先为了简化增删操作，可以将操作1和2（以下简称操作为op）合并，改为op1在头部插入矩阵A的同时还会在尾部插入一个单位阵E，同理op2在尾部插入矩阵B的同时还会在头部插入一个单位阵E，这样op3就变为同时在头尾删除一个矩阵。

由于操作和查询次数都是1e5，每次操作直接暴力模拟会超时，因此考虑使用分块算法，将所有操作分到 O(sqrt(n)) 个块中，每个块首先需要各自分别维护自身A矩阵和B矩阵的乘法前缀和（注意每次添加的单位阵E此时已经被算入其中）用于统计答案，维护一个sz变量记录当前块的有效块数量（也是前缀答案下标位置，具体见代码）；同时由于op3的存在，可能会出现当前某个前缀的矩阵已经被删干净，需要继续删除前面块的矩阵，因此还需要一个变量neg记录当前块中未匹配的删除数量（可以把这个过程看成一个括号序列匹配问题，op1/op2看作左括号，op3看作右括号，多出的右括号需要和前面的左括号匹配，当然，第一个块的情况除外，因为此时已经是空队列，可以忽略）

处理事件一时，只需要修改操作所在块的信息，时间复杂度为 O(sqrt(n))，为了加快速度，这里采用了惰性更新，记录新操作的信息的同时用一个布尔数组记录每个块是否需要被更新，在每次查询时再更新所需更新的块

对于事件二，当查询的位置在同一块内时，直接暴力统计块内答案，时间复杂度为 O(sqrt(n))，不在同一块内时，找到 l 和 r 所在的块以及所有中间块，暴力统计 l 和 r 所在块的答案，而后从右向左遍历中间块，一个变量neg记录过程中op3的数量，对于每一个块，对其减去op3的数量后累积到最终答案中，时间复杂度同样为 O(sqrt(n))，由此可以在理论上时间复杂度允许的情况下得到最终答案。

细节：本题细节还是很多的，我自己debug用了几乎一下午。。。主要还是要注意矩阵乘法的顺序，要按照正确的顺序维护前缀和，也正是因为如此，累计答案时也要分两部分维护（A矩阵和B矩阵部分），最后A部分的积矩阵乘B部分的积就是最终答案（主要是因为A矩阵插入在头部，B插入在尾部，这两部分的矩阵乘法顺序刚好相反，而一个块内可能既包含A也包含B，因此需要分开维护，至于单位阵E，由于其不会对结果产生任何影响，完全可以将其看作凑数的），另外从右向左遍历快处理是为了方便向前匹配op3。

余下的可以具体看代码注释。

代码

#pragma GCC optimize(2)
#pragma GCC optimize("inline")
#include <iostream>
#include <cmath>
using namespace std;

const int N = 100010, MXB = 320, MOD = 998244353;
struct Mat {  // 矩阵类
    int data[2][2];
    Mat(int a = 1, int b = 0, int c = 0, int d = 1) {
        // 构造矩阵，默认单位阵
        data[0][0] = a, data[0][1] = b;
        data[1][0] = c, data[1][1] = d;
    }

    Mat operator*(const Mat &o) const {
        Mat res(0, 0, 0, 0);
        for (int i = 0; i < 2; i++)
            for (int j = 0; j < 2; j++)
                for (int k = 0; k < 2; k++)
                    res.data[i][j] = (res.data[i][j] + 1ll * data[i][k] * o.data[k][j]) % MOD;
        return res;
    }

    inline void print() const {
        printf("%d %d %d %d\n", data[0][0], data[0][1], data[1][0], data[1][1]);
    }
};
using PMM = pair<Mat, Mat>;  // 矩阵乘积对，用作累计答案（first: sa, second: sb）

struct Op {
    int t;
    Mat mat;
} ops[N];  // 记录所有操作

int n, m, bsz, cntb;  // 块大小和块数量
bool lazy[MXB];  // 块是否需要惰性更新
/**
 * 注意：sz和neg可能会同时不为0，因为同一块内可能会出现一大波op3将sz减为0后增加neg，而后紧接着op1/op2
 * 此时neg需要作用于其前面的块答案，但不会影响当前块的答案（注意op3是对非空队列执行删除）
 */
struct Block {  // 块类，以每个块为单元记录信息
    int neg, sz;  // 待匹配的删除数量（操作3），可算入结果的前后矩阵数量（操作1/2）
    Mat sa[MXB], sb[MXB];  // 块内矩阵的乘法前缀和（分两边统计
    // 注：sz同时也指向两前缀和数组的最后一个有效元素
    void prod(int op, const Mat &mat) {  // 累积当前块内矩阵乘积
        sz++;  // 两侧各插入了一个矩阵，结果矩阵数量+1
        if (op == 1) {
            sa[sz] = mat * sa[sz - 1];
            sb[sz] = sb[sz - 1];
        } else {
            sa[sz] = sa[sz - 1];
            sb[sz] = sb[sz - 1] * mat;
        }
    }

    void update(int bi) {  // 更新块内信息
        sz = neg = 0;
        for (int i = bi * bsz, end = min(n, (bi + 1) * bsz); i < end; i++) {
            if (ops[i].t == 3) {
                sz ? sz-- : neg++;
                continue;
            }
            prod(ops[i].t, ops[i].mat);
        }
    }

    PMM query(int &neg) const {  // 查询当前块内的答案贡献
        int real_sz = max(0, sz - neg);  // 实际累积的矩阵数量
        neg = max(0, neg - sz) + this->neg;  // 更新待匹配删除数量（用于前块）
        return {sa[real_sz], sb[real_sz]};  // 分别返回两侧前缀和
    }
} blks[MXB];  // 块数组

PMM sec_query(int l, int r, int &neg) {
    // 查询区间段内的操作数量，分块算法保证 r - l + 1 < MXB
    Block tb = {0, 0, Mat(), Mat()};  // 临时块，用于计算左右两侧的答案
    for (int i = l; i <= r; i++) {
        switch (ops[i].t) {
            case 3:
                if (tb.sz > 0)  tb.sz--;
                else  tb.neg++;
                break;
            default:  // 操作1/2
                tb.prod(ops[i].t, ops[i].mat);
        }
    }
    int real_sz = max(0, tb.sz - neg);  // 减去后面待匹配的删除数量
    neg = max(0, neg - tb.sz) + tb.neg;  // 更新待匹配删除数量
    // 左右两侧的答案乘积
    return {tb.sa[real_sz], tb.sb[real_sz]};
}

int main() {
    scanf("%d%d", &n, &m);
    bsz = sqrt(n);
    cntb = (n + bsz - 1) / bsz;  // 计算块数量

    // 读入所有操作并预处理
    for (int i = 0; i < n; i++) {
        scanf("%d", &ops[i].t);
        int bi = i / bsz;  // 块号
        if (ops[i].t == 3) {  // 需要删除当前块内的头尾矩阵
            if (blks[bi].sz)  blks[bi].sz--;  // 矩阵数量减一
            else  blks[bi].neg++;  // 块内矩阵已被删空，未匹配的删除数量加一
        } else {  // 预处理当前块的信息
            int a, b, c, d;
            scanf("%d%d%d%d", &a, &b, &c, &d);
            ops[i].mat = Mat(a, b, c, d);
            blks[bi].prod(ops[i].t, ops[i].mat);
        }
    }

    // 处理所有查询
    while (m--) {
        int t;
        scanf("%d", &t);
        if (t == 1) {
            int i, t;
            scanf("%d%d", &i, &t);
            i--;  // 映射至[0, n)
            if (ops[i].t == 3 && t == 3)  continue;  // 特判掉无效更改
            int bi = i / bsz;  // 块号
            ops[i].t = t;  // 修改当前操作
            if (t != 3) {
                int a, b, c, d;
                scanf("%d%d%d%d", &a, &b, &c, &d);
                ops[i].mat = Mat(a, b, c, d);
            }
            lazy[bi] = true;  // 标记块需要惰性更新
        } else {
            int l, r, neg = 0;
            scanf("%d%d", &l, &r);
            l--, r--;  // 映射至[0, n)
            int bl = l / bsz, br = r / bsz;  // 左右块号
            PMM res{}, tmp{};
            if (bl == br) {  // 同一块内，直接暴力统计答案
                res = sec_query(l, r, neg);
            } else {
                res = sec_query(br * bsz, r, neg);  // 统计br块的答案
                for (int bi = br - 1; bi > bl; bi--) {  // 降序枚举中间块统计答案
                    if (lazy[bi]) {  // 惰性更新
                        blks[bi].update(bi);
                        lazy[bi] = false;
                    }
                    tmp = blks[bi].query(neg);  // 累积答案
                    res.first = res.first * tmp.first;  // 左乘左侧前缀和
                    res.second = tmp.second * res.second;  // 右乘右侧前缀和
                }
                // 统计bl块的答案
                tmp = sec_query(l, (bl + 1) * bsz - 1, neg);
                res.first = res.first * tmp.first;
                res.second = tmp.second * res.second;
            }
            (res.first * res.second).print();  // 输出答案
        }
    }

    return 0;
}

时间复杂度

O(N * sqrt(N))