csp 2023-12 宝藏

1.暴力35分

代码：

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const long long mod = 998244353;

struct node
{
    int opt;
    ll a1, a2, a3, a4;
    node(ll x1, ll x2, ll x3, ll x4, ll x5)
    {
        this->opt = x1;
        this->a1 = x2;
        this->a2 = x3;
        this->a3 = x4;
        this->a4 = x5;
    }
    node(int x)
    {
        this->opt = x;
    }
    node() {}
};

struct matrix
{
    ll a1, a2, a3, a4;
    matrix() {}
    matrix(ll x1, ll x2, ll x3, ll x4)
    {
        this->a1 = x1;
        this->a2 = x2;
        this->a3 = x3;
        this->a4 = x4;
    }
};

matrix mul(matrix a, matrix b)
{
    matrix tmp;
    tmp.a1 = (a.a1 * b.a1 % mod + a.a2 * b.a3 % mod) % mod;
    tmp.a2 = (a.a1 * b.a2 % mod + a.a2 * b.a4 % mod) % mod;
    tmp.a3 = (a.a3 * b.a1 % mod + a.a4 * b.a3 % mod) % mod;
    tmp.a4 = (a.a3 * b.a2 % mod + a.a4 * b.a4 % mod) % mod;
    return tmp;
}

int main()
{
    int n, m;
    cin >> n >> m;
    node ins[n + 1]; // 存放指令
    deque<pair<int, matrix>> dq;

    for (int i = 1; i <= n; i++)
    {
        int opt;
        cin >> opt;
        if (opt != 3)
        {
            ll x1, x2, x3, x4;
            cin >> x1 >> x2 >> x3 >> x4;
            ins[i] = node(opt, x1, x2, x3, x4);
        }
        else // 删除最晚插入的
            ins[i] = node(opt);
    }

    for (int i = 1; i <= m; i++)
    {
        int opt;
        cin >> opt;
        if (opt == 1)
        {
            int index;
            cin >> index;
            int new_opt;
            cin >> new_opt;
            if (new_opt == 3)
            {
                ins[index] = node(3);
            }
            else
            {
                ll x1, x2, x3, x4;
                cin >> x1 >> x2 >> x3 >> x4;
                ins[index] = node(new_opt, x1, x2, x3, x4);
            }
        }
        else
        {
            int l, r;
            cin >> l >> r;
            int cnt = 1;
            for (int j = l; j <= r; j++)
            {
                if (ins[j].opt == 1)
                {
                    dq.push_front(pair<int, matrix>(cnt++, matrix(ins[j].a1, ins[j].a2, ins[j].a3, ins[j].a4)));
                }
                else if (ins[j].opt == 2)
                {
                    dq.push_back(pair<int, matrix>(cnt++, matrix(ins[j].a1, ins[j].a2, ins[j].a3, ins[j].a4)));
                }
                else
                {
                    if (dq.size() != 0)
                    {
                        if (dq.front().first > dq.back().first)
                            dq.pop_front();
                        else
                            dq.pop_back();
                    }
                }
            }
            if (dq.size() == 0) // 队列为空，单位矩阵
            {
                cout << 1 << ' ' << 0 << ' ' << 0 << ' ' << 1 << endl;
            }
            else
            {
                matrix tmp = dq.front().second; // 队首元素
                dq.pop_front();
                while (dq.size() != 0)
                {
                    tmp = mul(tmp, dq.front().second);
                    dq.pop_front();
                }
                cout << tmp.a1 << " " << tmp.a2 << " " << tmp.a3 << " " << tmp.a4 << endl;
            }
        }
    }
    system("pause");
}

踩坑：

指令3的删除，不能直接根据存放的上一个指令来判断哪个指令是先插入的，因为ins数组中的上一个指令，可能是3指令，也可能是已经在deque里面删除了的指令，所以deque里面必须要有一个索引。