LOJ #2980. 「THUSCH 2017」大魔法师

zrzring 2020-08-24 AM 68℃ 0条

维护多元组之间的运算可以考虑矩阵,元素涉及到$A,B,C,v$四种,最后一个是参数,维护矩阵时多维护一个常数即可,那矩阵我们就维护一个$[A, B, C, 1]$,转移也比较容易考虑,区间修改可以用线段树维护,网上有说需要加法操作的题解,其实根本不需要,在矩阵中多维护一些常数就可以用乘法代替加法

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <queue>
#define ls x << 1
#define rs x << 1 | 1
using namespace std;
void file() {
    freopen("std.in", "r", stdin);
    freopen("wa.out", "w", stdout);
}
const int N = 1e6 + 10, inf = 1e9, dsq = 998244353;
inline int read() {
    bool sym = 0; int res = 0; char ch = getchar();
    while (!isdigit(ch)) sym |= (ch == '-'), ch = getchar();
    while (isdigit(ch)) res = (res << 3) + (res << 1) + (ch ^ 48), ch = getchar();
    return sym ? -res : res;
}
int mod(int x) {while (x > dsq) x -= dsq; return x;}
struct MAT {
    int n, m, mat[4][4];
    MAT() {
        n = m = 4; memset(mat, 0, sizeof(mat));
        for (int i = 0; i < 4; i++) mat[i][i] = 1;
    }
} a[N];
struct TREE {
    MAT sum, tag;
} tr[N];
MAT operator + (const MAT a, const MAT b) {
    MAT c; c.n = a.n; c.m = a.m;
    for (int i = 0; i < c.n; i++) {
        for (int j = 0; j < c.m; j++) {
            c.mat[i][j] = mod(a.mat[i][j] + b.mat[i][j]);
        }
    }
    return c;
}
MAT operator * (const MAT a, const MAT b) {
    MAT c; c.n = a.n; c.m = b.m; memset(c.mat, 0, sizeof(c.mat));
    for (int i = 0; i < c.n; i++) {
        for (int j = 0; j < c.m; j++) {
            for (int k = 0; k < a.m; k++) {
                c.mat[i][j] = mod(c.mat[i][j] + 1ll * a.mat[i][k] * b.mat[k][j] % dsq);
            }
        }
    }
    return c;
}
bool operator == (const MAT a, const MAT b) {
    if (a.n != b.n || a.m != b.m) return 0;
    for (int i = 0; i < a.n; i++) {
        for (int j = 0; j < a.m; j++) {
            if (a.mat[i][j] != b.mat[i][j]) return 0;
        }
    }
    return 1;
}
int n, m;
void pushup(int x) {tr[x].sum = tr[ls].sum + tr[rs].sum;}
void build(int x, int l, int r) {
    if (l == r) {tr[x].sum = a[l]; return;}
    int mid = l + r >> 1; build(ls, l, mid); build(rs, mid + 1, r); pushup(x);
}
void update(int x, int l, int r, MAT t) {
    tr[x].tag = tr[x].tag * t; tr[x].sum = tr[x].sum * t;
}
void pushdown(int x, int l, int r, int mid) {
    if (tr[x].tag == a[0]) return;
    update(ls, l, mid, tr[x].tag);
    update(rs, mid + 1, r, tr[x].tag);
    tr[x].tag = a[0];
}
void modify(int x,int l, int r, int ln, int rn, MAT t) {
    if (ln <= l && r <= rn) {update(x, l, r, t); return;}
    int mid = l + r >> 1; pushdown(x, l, r, mid);
    if (mid >= ln) modify(ls, l, mid, ln, rn, t);
    if (mid + 1 <= rn) modify(rs, mid + 1, r, ln, rn, t);
    pushup(x);
}
MAT query(int x, int l, int r, int ln, int rn) {
    if (ln <= l && r <= rn) return tr[x].sum;
    int mid = l + r >> 1; pushdown(x, l, r, mid);
    if (mid >= rn) return query(ls, l, mid, ln, rn);
    if (mid + 1 <= ln) return query(rs, mid + 1, r, ln, rn);
    return query(ls, l, mid, ln, rn) + query(rs, mid + 1, r, ln, rn);
}
void write(MAT a) {
    for (int i = 1; i < 4; i++) printf("%d ", a.mat[0][i]); printf("\n");
}
int main() {
    n = read();
    for (int i = 1; i <= n; i++) {
        a[i].n = 1; a[i].m = 4;
        a[i].mat[0][0] = 1; a[i].mat[0][1] = read(); a[i].mat[0][2] = read(); a[i].mat[0][3] = read(); 
    }
    build(1, 1, n); m = read();
    for (int i = 1; i <= m; i++) {
        int opt = read(), l = read(), r = read(), v; MAT t;
        if (opt == 1) t.mat[2][1] = 1;
        if (opt == 2) t.mat[3][2] = 1;
        if (opt == 3) t.mat[1][3] = 1;
        if (opt == 4) v = read(), t.mat[0][1] = v;
        if (opt == 5) v = read(), t.mat[2][2] = v;
        if (opt == 6) v = read(), t.mat[3][3] = 0, t.mat[0][3] = v;
        if (opt == 7) {MAT ans = query(1, 1, n, l, r); write(ans);}
        if (opt != 7) modify(1, 1, n, l, r, t);
    }
    return 0;
}

评论


您还没有登录呦


登录 注册
Title - Artist
0:00