P7453

__vector__ · 2023-10-01 23:00:16 · 个人记录

题解：

#include <bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for (int i = a; i <= b; i++)
#define REP(i, a, b) for (int i = a; i >= b; i--)
typedef long long ll;
typedef pair<int, int> pii;
const int maxn = 250005;
const ll mod = 998244353;
ll qpow(ll a, ll b)
{
    ll ret = 1;
    while (b)
    {
        if (b & 1)
            ret = ret * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return ret;
}
ll inv(ll a)
{
    return qpow(a, mod - 2);
}
int n, m;
ll a[maxn], b[maxn], c[maxn];
struct Matrix
{
    ll mp[3][3];
    void init()
    {
        memset(mp, 0, sizeof mp);
    }
    void unit()
    {
        memset(mp, 0, sizeof mp);
        mp[0][0] = mp[1][1] = mp[2][2] = 1;
    }
    bool isunit()const
    {
        if (mp[0][0] != 1)
            return 0;
        if (mp[0][1] != 0)
            return 0;
        if (mp[0][2] != 0)
            return 0;
        if (mp[1][0] != 0)
            return 0;
        if (mp[1][1] != 1)
            return 0;
        if (mp[1][2] != 0)
            return 0;
        if (mp[2][0] != 0)
            return 0;
        if (mp[2][1] != 0)
            return 0;
        if (mp[2][2] != 1)
            return 0;
        return 1;
    }
    bool iszero()const
    {
        if (mp[0][0] != 0)
            return 0;
        if (mp[0][1] != 0)
            return 0;
        if (mp[0][2] != 0)
            return 0;
        if (mp[1][0] != 0)
            return 0;
        if (mp[1][1] != 0)
            return 0;
        if (mp[1][2] != 0)
            return 0;
        if (mp[2][0] != 0)
            return 0;
        if (mp[2][1] != 0)
            return 0;
        if (mp[2][2] != 0)
            return 0;
        return 1;
    }
    Matrix operator+(const Matrix &b) const
    {
        Matrix res;
        res.mp[0][0] = mp[0][0] + b.mp[0][0];
        res.mp[0][0] %= mod;
        res.mp[0][1] = mp[0][1] + b.mp[0][1];
        res.mp[0][1] %= mod;
        res.mp[0][2] = mp[0][2] + b.mp[0][2];
        res.mp[0][2] %= mod;
        res.mp[1][0] = mp[1][0] + b.mp[1][0];
        res.mp[1][0] %= mod;
        res.mp[1][1] = mp[1][1] + b.mp[1][1];
        res.mp[1][1] %= mod;
        res.mp[1][2] = mp[1][2] + b.mp[1][2];
        res.mp[1][2] %= mod;
        res.mp[2][0] = mp[2][0] + b.mp[2][0];
        res.mp[2][0] %= mod;
        res.mp[2][1] = mp[2][1] + b.mp[2][1];
        res.mp[2][1] %= mod;
        res.mp[2][2] = mp[2][2] + b.mp[2][2];
        res.mp[2][2] %= mod;
        return res;
    }
    Matrix operator*(const Matrix &b) const
    {
        Matrix res;
        res.init();
        res.mp[0][0] += mp[0][0] * b.mp[0][0];
        res.mp[0][1] += mp[0][0] * b.mp[0][1];
        res.mp[0][2] += mp[0][0] * b.mp[0][2];
        res.mp[0][0] += mp[0][1] * b.mp[1][0];
        res.mp[0][1] += mp[0][1] * b.mp[1][1];
        res.mp[0][2] += mp[0][1] * b.mp[1][2];
        res.mp[0][0] += mp[0][2] * b.mp[2][0];
        res.mp[0][1] += mp[0][2] * b.mp[2][1];
        res.mp[0][2] += mp[0][2] * b.mp[2][2];
        res.mp[1][0] += mp[1][0] * b.mp[0][0];
        res.mp[1][1] += mp[1][0] * b.mp[0][1];
        res.mp[1][2] += mp[1][0] * b.mp[0][2];
        res.mp[1][0] += mp[1][1] * b.mp[1][0];
        res.mp[1][1] += mp[1][1] * b.mp[1][1];
        res.mp[1][2] += mp[1][1] * b.mp[1][2];
        res.mp[1][0] += mp[1][2] * b.mp[2][0];
        res.mp[1][1] += mp[1][2] * b.mp[2][1];
        res.mp[1][2] += mp[1][2] * b.mp[2][2];
        res.mp[2][0] += mp[2][0] * b.mp[0][0];
        res.mp[2][1] += mp[2][0] * b.mp[0][1];
        res.mp[2][2] += mp[2][0] * b.mp[0][2];
        res.mp[2][0] += mp[2][1] * b.mp[1][0];
        res.mp[2][1] += mp[2][1] * b.mp[1][1];
        res.mp[2][2] += mp[2][1] * b.mp[1][2];
        res.mp[2][0] += mp[2][2] * b.mp[2][0];
        res.mp[2][1] += mp[2][2] * b.mp[2][1];
        res.mp[2][2] += mp[2][2] * b.mp[2][2];
        res.mp[0][0] %= mod;
        res.mp[0][1] %= mod;
        res.mp[0][2] %= mod;
        res.mp[1][0] %= mod;
        res.mp[1][1] %= mod;
        res.mp[1][2] %= mod;
        res.mp[2][0] %= mod;
        res.mp[2][1] %= mod;
        res.mp[2][2] %= mod;
        return res;
    }
    Matrix operator*(const ll &b)
    {
        Matrix res;
        res.mp[0][0] = mp[0][0] * b;
        res.mp[0][0] %= mod;
        res.mp[0][1] = mp[0][1] * b;
        res.mp[0][1] %= mod;
        res.mp[0][2] = mp[0][2] * b;
        res.mp[0][2] %= mod;
        res.mp[1][0] = mp[1][0] * b;
        res.mp[1][0] %= mod;
        res.mp[1][1] = mp[1][1] * b;
        res.mp[1][1] %= mod;
        res.mp[1][2] = mp[1][2] * b;
        res.mp[1][2] %= mod;
        res.mp[2][0] = mp[2][0] * b;
        res.mp[2][0] %= mod;
        res.mp[2][1] = mp[2][1] * b;
        res.mp[2][1] %= mod;
        res.mp[2][2] = mp[2][2] * b;
        res.mp[2][2] %= mod;
        return res;
    }
};
struct SegmentTree
{
    Matrix val[maxn << 2];
    Matrix mul[maxn << 2];
    Matrix add[maxn << 2];
    int L[maxn << 2], R[maxn << 2];
    int len(int pos)
    {
        return R[pos] - L[pos] + 1;
    }
    void pushup(int pos)
    {
        val[pos].mp[0][0]=val[pos<<1].mp[0][0]+val[pos<<1|1].mp[0][0];
        val[pos].mp[0][1]=val[pos<<1].mp[0][1]+val[pos<<1|1].mp[0][1];
        val[pos].mp[0][2]=val[pos<<1].mp[0][2]+val[pos<<1|1].mp[0][2];
        val[pos].mp[0][0]%=mod;
        val[pos].mp[0][1]%=mod;
        val[pos].mp[0][2]%=mod;
    }
    void Add(int pos, ll _val, int id)
    {
        Matrix ml, ad;
        if (id == 1)
        {
            ml.init();
            ml.mp[0][0] = ml.mp[1][0] = ml.mp[1][1] = ml.mp[2][2] = 1;
            ad.init();
        }
        else if (id == 2)
        {
            ml.init();
            ml.mp[0][0] = ml.mp[1][1] = ml.mp[2][1] = ml.mp[2][2] = 1;
            ad.init();
        }
        else if (id == 3)
        {
            ml.init();
            ml.mp[0][0] = ml.mp[1][1] = ml.mp[2][2] = ml.mp[0][2] = 1;
            ad.init();
        }
        else if (id == 4)
        {
            ml.unit();
            ad.init();
            ad.mp[0][0] = _val;
        }
        else if (id == 5)
        {
            ml.init();
            ml.mp[0][0] = 1;
            ml.mp[1][1] = _val;
            ml.mp[2][2] = 1;
            ad.init();
        }
        else if (id == 6)
        {
            ml.init();
            ml.mp[0][0] = 1;
            ml.mp[1][1] = 1;
            ad.init();
            ad.mp[0][2] = _val;
        }
        val[pos] = val[pos] * ml;
        val[pos] = val[pos] + ad * len(pos);
        mul[pos] = mul[pos] * ml;
        add[pos] = add[pos] * ml;
        add[pos] = add[pos] + ad;
    }
    void pushdown(int pos)
    {
        if (!mul[pos].isunit())
        {
            val[pos << 1] = val[pos << 1] * mul[pos];
            mul[pos << 1] = mul[pos << 1] * mul[pos];
            add[pos << 1] = add[pos << 1] * mul[pos];
            val[pos << 1 | 1] = val[pos << 1 | 1] * mul[pos];
            mul[pos << 1 | 1] = mul[pos << 1 | 1] * mul[pos];
            add[pos << 1 | 1] = add[pos << 1 | 1] * mul[pos];
            mul[pos].unit();
        }
        if (!mul[pos].iszero())
        {
            val[pos << 1] = val[pos << 1] + add[pos] * len(pos << 1);
            add[pos << 1] = add[pos << 1] + add[pos];
            val[pos << 1 | 1] = val[pos << 1 | 1] + add[pos] * len(pos << 1 | 1);
            add[pos << 1 | 1] = add[pos << 1 | 1] + add[pos];
            add[pos].init();
        }
    }
    void build(int pos, int l, int r)
    {
        L[pos] = l, R[pos] = r;
        mul[pos].unit();
        add[pos].init();
        if (l == r)
        {
            val[pos].init();
            val[pos].mp[0][0] = a[l];
            val[pos].mp[0][1] = b[l];
            val[pos].mp[0][2] = c[l];
            return;
        }
        int mid = (l + r) >> 1;
        build(pos << 1, l, mid);
        build(pos << 1 | 1, mid + 1, r);
        pushup(pos);
    }
    void chg(int pos, int l, int r, ll _val, int id)
    {
        if (R[pos] < l || L[pos] > r)
            return;
        if (L[pos] >= l && R[pos] <= r)
        {
            Add(pos, _val, id);
            return;
        }
        pushdown(pos);
        int mid = (L[pos] + R[pos]) >> 1;
        if (mid >= l)
            chg(pos << 1, l, r, _val, id);
        if (mid < r)
            chg(pos << 1 | 1, l, r, _val, id);
        pushup(pos);
    }
    Matrix query(int pos, int l, int r)
    {
        if (R[pos] < l || L[pos] > r)
        {
            Matrix res;
            res.init();
            return res;
        }
        if (L[pos] >= l && R[pos] <= r)
        {
            return val[pos];
        }
        pushdown(pos);
        int mid = (L[pos] + R[pos]) >> 1;
        Matrix res;
        res.init();
        if (mid >= l)
            res = res + query(pos << 1, l, r);
        if (mid < r)
            res = res + query(pos << 1 | 1, l, r);
        return res;
    }
} SGT;
int main()
{
    scanf("%d", &n);
    FOR(i, 1, n)
    {
        scanf("%lld%lld%lld", &a[i], &b[i], &c[i]);
    }
    SGT.build(1, 1, n);
    scanf("%d", &m);
    while (m--)
    {
        int op, l, r;
        ll v;
        scanf("%d%d%d", &op, &l, &r);
        if (op == 1)
        {
            SGT.chg(1, l, r, -1, 1);
        }
        else if (op == 2)
        {
            SGT.chg(1, l, r, -1, 2);
        }
        else if (op == 3)
        {
            SGT.chg(1, l, r, -1, 3);
        }
        else if (op == 4)
        {
            scanf("%lld", &v);
            SGT.chg(1, l, r, v, 4);
        }
        else if (op == 5)
        {
            scanf("%lld", &v);
            SGT.chg(1, l, r, v, 5);
        }
        else if (op == 6)
        {
            scanf("%lld", &v);
            SGT.chg(1, l, r, v, 6);
        }
        else if (op == 7)
        {
            Matrix ans = SGT.query(1l, l, r);
            printf("%lld %lld %lld\n", ans.mp[0][0], ans.mp[0][1], ans.mp[0][2]);
        }
    }
    return 0;
}