LOJ2980. 「THUSCH 2017」大魔法师

一道好题

Solution

区间操作，容易想到线段树
但是普通的线段树好像无法维护这种区间操作
考虑将操作转换成矩阵乘法，再用线段树维护矩阵

这里的操作有两种转换方法：
1.转换成矩阵的乘法和加法：
线段树维护区间矩阵和
优势：空间和时间复杂度的常数要小
缺点：有优先级问题（类似于线段树模板1和线段树模板2的区别）

2.全部转换成矩阵的乘法：
线段树维护区间矩阵乘积
优势：只用维护区间乘积，无优先级问题
缺点：时空复杂度的常数比方法1略大

两种方法各有利弊，根据题目要求具体选择

#include <bits/stdc++.h>

using namespace std;
const int MAXN = 2.5e5 + 10;
const int MOD = 998244353;
typedef long long ll;
#define rint register int
int n, m;
#define lson (node << 1)
#define rson (node << 1 | 1)
#define mid ((l + r) >> 1)
inline int Add(int a, int b) { return (a += b) >= MOD ? a - MOD : a; }
struct Matrix {
    int a[3][3], n, m;
    inline void Clear(void) { memset(a, 0, sizeof(a)); }
    inline Matrix(const int _n = 0, const int _m = 0) {
        n = _n;
        m = _m;
        Clear();
    }
    inline void IOne(void) {
        for (register int i = 0; i < n; ++i) a[i][i] = 1;
    }
    inline void Init(const int _n, const int _m) {
        n = _n;
        m = _m;
    }
    Matrix operator+(const Matrix &p) const {
        Matrix c(n, m);
        for (register int i = 0; i < n; ++i) {
            for (register int j = 0; j < m; ++j) {
                c.a[i][j] = Add(a[i][j], p.a[i][j]);
            }
        }
        return c;
    }
    Matrix operator*(const int p) const {
        Matrix c(n, m);
        for (register int i = 0; i < n; ++i) {
            for (register int j = 0; j < m; ++j) {
                c.a[i][j] = (long long)a[i][j] * p % MOD;
            }
        }
        return c;
    }
    Matrix operator*(const Matrix &p) const {
        Matrix c(n, p.m);
        for (register int i = 0; i < n; ++i) {
            for (register int k = 0; k < m; ++k) {
                for (register int j = 0; j < p.m; ++j)
                    c.a[i][j] = Add(c.a[i][j], (ll)a[i][k] * p.a[k][j] % MOD);
            }
        }
        return c;
    }
};
Matrix data[MAXN << 2], tmul[MAXN << 2], tadd[MAXN << 2];
void build(int node, int l, int r) {
    data[node].Init(1, 3);
    tmul[node].Init(3, 3);
    tmul[node].IOne();
    tadd[node].Init(1, 3);
    if (l == r) {
        for (register int i = 0; i < 3; ++i) scanf("%d", &data[node].a[0][i]);
        return;
    }
    build(lson, l, mid);
    build(rson, mid + 1, r);
    data[node] = data[lson] + data[rson];
}
inline void pushdown(int node, int l, int r) {
    tmul[lson] = tmul[lson] * tmul[node];
    tmul[rson] = tmul[rson] * tmul[node];
    tadd[lson] =  tadd[lson]* tmul[node] + tadd[node];
    tadd[rson] =  tadd[rson] * tmul[node] + tadd[node];
    data[lson] = data[lson] * tmul[node] + tadd[node] * (mid - l + 1);
    data[rson] = data[rson] * tmul[node] + tadd[node] * (r - mid);
    tmul[node].Clear();
    tmul[node].IOne();
    tadd[node].Clear();
}

void change(int node, int l, int r, int from, int to, Matrix val, int type) {
    if (from > r || to < l)
        return;
    if (from <= l && r <= to) {
        if (type == 0)
            tmul[node] = tmul[node] * val, tadd[node] = tadd[node] * val, data[node] = data[node] * val;
        else
            tadd[node] = tadd[node] + val, data[node] = data[node] + val * (r - l + 1);
        return;
    }
    pushdown(node, l, r);
    change(lson, l, mid, from, to, val, type);
    change(rson, mid + 1, r, from, to, val, type);
    data[node] = data[lson] + data[rson];
}
Matrix query(int node, int l, int r, int from, int to) {
    if (from <= l && r <= to)
        return data[node];
    pushdown(node, l, r);
    Matrix ret(1, 3);
    if (from <= mid)
        ret = ret + query(lson, l, mid, from, to);
    if (to > mid)
        ret = ret + query(rson, mid + 1, r, from, to);
    return ret;
}
inline void init(void) {
    scanf("%d", &n);
    build(1, 1, n);
    scanf("%d", &m);
}

inline void work(void) {
    Matrix m1(3, 3), m2(3, 3), m3(3, 3), p4(1, 3), m5(3, 3), m6(3, 3), p6(1, 3);
    m1.a[0][0] = m1.a[1][0] = m1.a[1][1] = m1.a[2][2] = 1;
    m2.a[0][0] = m2.a[1][1] = m2.a[2][1] = m2.a[2][2] = 1;
    m3.a[0][0] = m3.a[1][1] = m3.a[0][2] = m3.a[2][2] = 1;
    m5.a[0][0] = m5.a[2][2] = m6.a[0][0] = m6.a[1][1] = 1;
    int op, l, r;
    for (register int i = 1; i <= m; ++i) {
        scanf("%d%d%d", &op, &l, &r);
        if (op == 1)
            change(1, 1, n, l, r, m1, 0);
        if (op == 2)
            change(1, 1, n, l, r, m2, 0);
        if (op == 3)
            change(1, 1, n, l, r, m3, 0);
        if (op == 4)
            scanf("%d", &p4.a[0][0]), change(1, 1, n, l, r, p4, 1);
        if (op == 5)
            scanf("%d", &m5.a[1][1]), change(1, 1, n, l, r, m5, 0);
        if (op == 6)
            scanf("%d", &p6.a[0][2]), change(1, 1, n, l, r, m6, 0), change(1, 1, n, l, r, p6, 1);
        if (op == 7) {
            Matrix now = query(1, 1, n, l, r);
            printf("%d %d %d\n", now.a[0][0], now.a[0][1], now.a[0][2]);
        }
    }
}

int main() {
    init();
    work();
    return 0;
}

LOJ2980. 「THUSCH 2017」大魔法师

原文：https://www.cnblogs.com/FlySakura/p/11625965.html