参考题解

算法：分块

对于指令 $1, \ 2$，如果只从单个方向考虑将它们的矩阵插入双端队列 $q$，那将指令 $3$ 将会很难操作，所以我们不妨将指令 $1, \ 2, \ 3$ 扩展一下：

• 指令 $1$：在 队首 插入矩阵 $A$，在 队尾 插入单位矩阵 $E$
• 指令 $2$：在 队尾 插入矩阵 $B$，在 队首 插入单位矩阵 $E$
• 指令 $3$：如果队列 非空，同时取出队首和队尾的矩阵

这样一来，我们就无需记录哪一边（队首或队尾）是最晚插入的。

同时，这就变成了一个括号序列问题，即把指令 $1, \ 2$ 看成是 (，把指令 $3$ 看成是 )。

考虑分块维护信息。每个块内维护如下信息：

• $l, \ r$：当前块的左右端点（我喜欢左闭右开 $[l, \ r)$，喜欢双侧闭区间的下面代码要改）
• $push, \ pop$：在经过括号匹配以后，一定会得到这样的序列 )))((，即左边有可能有一些指令 $3$ 完全是空操作（在空队列上操作），右边有可能有一些指令 $1, \ 2$ 没法完全被指令 $3$ 所匹配，所以记 ) 数量为 $pop$，记 ( 数量为 $push$
• $sL, \ sR$：它们的有效下标区间为 $[1, \ push]$，表示从 $l$ 到 $r$ 剩下的 ( 的矩阵前缀积；$sL$ 是左矩阵（即插入队首的矩阵）的前缀积，$sR$ 是右矩阵（即插入队尾的矩阵）的前缀积。注意左矩阵的前缀积其实是从队列中心往左的矩阵的乘积（想象一个双端队列，越晚的操作应该越靠近左侧的队首）

然后对于每一个事件：

• 事件 $1$：直接找到对应下标所在块，改完对应下标的指令后，把这个块从 $[l, \ r)$ 重新初始化一遍
• 事件 $2$：设给定区间为 $[L, \ R]$。我们从右往左看（因为矩阵乘操作如果有一方不可逆就没办法撤销），分为三部分。
  • 在 $R$ 所在块，我们暴力做一遍上述初始化 $sL, \ sR$ 的操作，注意记录 $pop’$
  • 往前一直到 $L$ 所在块的下一块。在这个过程中，又有两种情况。设当前块下标为 $i$
    • $block[i].push \leqslant pop’$，说明右侧过来的指令 $3$ 多到 $i$ 这个块内无法剩下任何矩阵，因此令 $pop’ = pop’ - block[i].push + block[i].pop$，意思就是先和 ( 匹配，再加上 )（想象上述的 )))((）
    • $block[i].push \gt pop’$，说明右侧过来的指令 $3$ 不多，那么我们的 $sL$ 和 $sR$ 就能有作用，但有效区间变为 $[1, \ block[i].push - pop’]$，同时最后记得也要将 $pop’$ 变为前面的 )，即 $pop’ = block[i].pop$
  • 在 $L$ 所在块，我们同样暴力做一遍上述初始化 $sL, \ sR$ 的操作，但是无需记录 $pop$，因为最前面的 ) 已经无法影响结果，所以只要把右侧传过来的 $pop’$ 和 当前块产生的的 $push’$ 相互匹配一下

经历了三次优化

全用 STL 和匿名函数 $\Rightarrow$ 部分使用数组并全用全局函数 $\Rightarrow$ 全部使用数组和全局函数，且改为结构体内 init

时间复杂度 $O(n^{\frac{3}{2}})$

C++ Code

#pragma GCC optimize(2, 3, "Ofast", "inline")

#include <bits/stdc++.h>

using i64 = int64_t;
using u64 = uint64_t;
using f64 = double_t;
using i128 = __int128_t;

constexpr int P = 998244353;

struct Matrix {
    int mat[2][2];
    Matrix(int diag = 1) {
        mat[0][0] = mat[1][1] = diag;
        mat[0][1] = mat[1][0] = 0;
    }
    void init(int diag = 1) {
        mat[0][0] = mat[1][1] = diag;
        mat[0][1] = mat[1][0] = 0;
    }
    friend Matrix operator*(const Matrix &a, const Matrix &b) {
        Matrix c(0);
        for (int i = 0; i < 2; i++) {
            for (int j = 0; j < 2; j++) {
                for (int k = 0; k < 2; k++) {
                    c.mat[i][j] += i64(a.mat[i][k]) * b.mat[k][j] % P;
                    if (c.mat[i][j] >= P) {
                        c.mat[i][j] -= P;
                    }
                }
            }
        }
        return c;
    }
    friend std::istream &operator>>(std::istream &is, Matrix &mat) {
        for (int x = 0; x < 2; x++) {
            for (int y = 0; y < 2; y++) {
                is >> mat.mat[x][y];
            }
        }
        return is;
    }
    friend std::ostream &operator<<(std::ostream &os, const Matrix &mat) {
        for (int x = 0; x < 2; x++) {
            for (int y = 0; y < 2; y++) {
                os << mat.mat[x][y] << " \n"[x == 1 and y == 1];
            }
        }
        return os;
    }
};

struct Operation {
    int o = 0;
    Matrix matL;
    Matrix matR;
    friend std::istream &operator>>(std::istream &is, Operation &op) {
        is >> op.o;
        if (op.o == 1) {
            for (int x = 0; x < 2; x++) {
                for (int y = 0; y < 2; y++) {
                    is >> op.matL.mat[x][y];
                }
            }
            op.matR.init();
        } else if (op.o == 2) {
            for (int x = 0; x < 2; x++) {
                for (int y = 0; y < 2; y++) {
                    is >> op.matR.mat[x][y];
                }
            }
            op.matL.init();
        }
        return is;
    }
    friend std::ostream &operator<<(std::ostream &os, const Operation &op) {
        os << "op type = " << op.o << "\n";
        os << "matL = \n" << op.matL.mat;
        os << "matR = \n" << op.matR.mat;
        os << "\n";
        return os;
    }
};

constexpr int N = 100000;
constexpr int BN = std::sqrt(N);

int n, m;
Operation op[N + 1];

int len;
std::vector<int> q;

struct Block {
    int l = 0;
    int r = 0;
    int push = 0;
    int pop = 0;
    Matrix sL[BN + 1];
    Matrix sR[BN + 1];

    void init(int idx) {
        l = idx * len;
        r = std::min(l + len, n);
        pop = 0;
        q.clear();
        for (int i = l; i < r; i++) {
            if (op[i].o != 3) {
                q.push_back(i);
            } else if (!q.empty()) {
                q.pop_back();
            } else {
                pop++;
            }
        }
        push = q.size();
        for (int i = 0; i < q.size(); i++) {
            sL[i + 1] = op[q[i]].matL * sL[i];
            sR[i + 1] = sR[i] * op[q[i]].matR;
        }
    }
};
Block block[N / BN + 1];

Matrix query(int l, int r) {
    int bl = l / len;
    int br = (r - 1) / len + 1;
    if (br - bl == 1) {
        q.clear();
        for (int i = l; i < r; i++) {
            if (op[i].o != 3) {
                q.push_back(i);
            } else if (!q.empty()) {
                q.pop_back();
            }
        }
        Matrix ansL;
        Matrix ansR;
        for (int i: q) {
            ansL = op[i].matL * ansL;
            ansR = ansR * op[i].matR;
        }
        return ansL * ansR;
    }
    int pop = 0;
    q.clear();
    for (int i = block[br - 1].l; i < r; i++) {
        if (op[i].o != 3) {
            q.push_back(i);
        } else if (!q.empty()) {
            q.pop_back();
        } else {
            pop++;
        }
    }
    Matrix ansL;
    Matrix ansR;
    for (int i: q) {
        ansL = op[i].matL * ansL;
        ansR = ansR * op[i].matR;
    }
    for (int i = br - 2; i > bl; i--) {
        int push = block[i].push;
        if (push <= pop) {
            pop -= push;
            pop += block[i].pop;
        } else {
            ansL = ansL * block[i].sL[push - pop];
            ansR = block[i].sR[push - pop] * ansR;
            pop = block[i].pop;
        }
    }
    q.clear();
    for (int i = l; i < block[bl].r; i++) {
        if (op[i].o != 3) {
            q.push_back(i); 
        } else if (!q.empty()) {
            q.pop_back();
        }
    }
    while (pop > 0 and !q.empty()) {
        q.pop_back();
        pop--;
    }
    for (int i = int(q.size()) - 1; i >= 0; i--) {
        ansL = ansL * op[q[i]].matL;
        ansR = op[q[i]].matR * ansR;
    }
    return ansL * ansR;
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    std::cout << std::fixed << std::setprecision(12);

    std::cin >> n >> m;
    for (int i = 0; i < n; i++) {
        std::cin >> op[i];
    }
    // for (const auto &o: op) {
    //     std::cout << o << "\n";
    // }

    len = std::sqrt(n);
    for (int i = 0; i < n; i += len) {
        block[i / len].init(i / len);
    }

    while (m--) {
        int v;
        std::cin >> v;

        if (v == 1) {
            int i;
            std::cin >> i;
            i--;

            std::cin >> op[i];
            block[i / len].init(i / len);
        } else {
            int l, r;
            std::cin >> l >> r;
            l--;

            std::cout << query(l, r);
        }
    }

    return 0;
}