RT,代码如下:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int ll
#define rep(i, l, r) for(int i = l;i <= r; ++ i)
#define per(i, r, l) for(int i = r;i >= l; -- i)
const int mod = 998244353;
const int maxn = 250005;
int n, m, val[maxn][3];
struct matrix {
int a[6][6], n, m;
inline void init () {
rep (i, 0, 5) {
rep (j, 0, 5) {
a[i][j] = 0;
}
}
}
inline void initI (int x) {
init ();
rep (i, 1, x) a[i][i] = 1;
}
} m1, m2, m3;
matrix operator * (matrix a, matrix b) {
matrix c;
c.init ();
if (a.m == b.n) ;
else swap (a, b);
c.n = a.n;
c.m = b.m;
rep (i, 1, c.n) {
rep (j, 1, c.m) {
rep (k, 1, a.m) {
c.a[i][j] = (c.a[i][j] + a.a[i][k] * b.a[k][j] % mod) % mod;
}
}
}
return c;
}
matrix operator + (matrix a, matrix b) {
matrix c;
c.init ();
c.n = a.n, c.m = a.m;
rep (i, 1, a.n) {
rep (j, 1, a.m) {
c.a[i][j] = (a.a[i][j] + b.a[i][j]) % mod;
}
}
if (a.n == 1 && a.m == 4) c.a[1][4] = 1;
return c;
}
matrix sum[maxn << 2], inc[maxn << 2];
inline void push_up (int u) {
sum[u] = sum[u << 1] + sum[u << 1 | 1];
}
inline void push_down (int u, int l, int r) {
sum[u << 1] = sum[u << 1] * inc[u];
sum[u << 1 | 1] = sum[u << 1 | 1] * inc[u];
inc[u << 1] = inc[u << 1] * inc[u];
inc[u << 1 | 1] = inc[u << 1 | 1] * inc[u];
inc[u].init ();
inc[u].initI (4);
}
inline void build (int u, int l, int r) {
sum[u].n = 1;
sum[u].m = 4;
inc[u].n = inc[u].m = 4;
inc[u].initI (4);
if (l == r) {
sum[u].a[1][1] = val[l][0];
sum[u].a[1][2] = val[l][1];
sum[u].a[1][3] = val[l][2];
sum[u].a[1][4] = 1;
return ;
}
int mid = l + r >> 1;
build (u << 1, l, mid);
build (u << 1 | 1, mid + 1, r);
push_up (u);
}
inline void upd (int u, int l, int r, int x, int y, matrix mtx) {
if (x <= l && r <= y) {
inc[u] = inc[u] * mtx;
sum[u] = sum[u] * mtx;
return ;
}
push_down (u, l, r);
int mid = l + r >> 1;
if (x <= mid) upd (u << 1, l, mid, x, y, mtx);
if (y > mid) upd (u << 1 | 1, mid + 1, r, x, y, mtx);
push_up (u);
}
inline matrix query (int u, int l, int r, int x, int y) {
if (x <= l && r <= y) return sum[u];
push_down (u, l, r);
int mid = l + r >> 1;
matrix ans;
ans.n = 1, ans.m = 4;
ans.a[1][1] = ans.a[1][2] = ans.a[1][3] = 0;
ans.a[1][4] = 1;
if (x <= mid) ans = ans + (matrix) (query (u << 1, l, mid, x, y));
if (y > mid) ans = ans + (matrix) (query (u << 1 | 1, mid + 1, r, x, y));
return ans;
}
signed main () {
m1.n = m1.m = 4;
m1.init ();
m1.a[1][1] = m1.a[2][1] = m1.a[2][2] = m1.a[3][3] = m1.a[4][4] = 1;
m2.n = m2.m = 4;
m2.init ();
m2.a[1][1] = m2.a[2][2] = m2.a[3][2] = m2.a[3][3] = m2.a[4][4] = 1;
m3.n = m3.m = 4;
m3.init ();
m3.a[1][1] = m3.a[1][3] = m3.a[2][2] = m3.a[3][3] = m3.a[4][4] = 1;
scanf ("%lld", &n);
rep (i, 1, n) scanf ("%lld %lld %lld", &val[i][0], &val[i][1], &val[i][2]);
build (1, 1, n);
scanf ("%lld", &m);
while (m --) {
int op, l, r, v;
scanf ("%lld %lld %lld", &op, &l, &r);
if (op == 1) upd (1, 1, n, l, r, m1);
else if (op == 2) upd (1, 1, n, l, r, m2);
else if (op == 3) upd (1, 1, n, l, r, m3);
else if (op == 4) {
scanf ("%lld", &v);
matrix mtx;
mtx.n = mtx.m = 4;
mtx.init ();
mtx.a[1][1] = mtx.a[2][2] = mtx.a[3][3] = mtx.a[4][4] = 1;
mtx.a[4][1] = v;
upd (1, 1, n, l, r, mtx);
}
else if (op == 5) {
scanf ("%lld", &v);
matrix mtx;
mtx.n = mtx.m = 4;
mtx.init ();
mtx.a[1][1] = mtx.a[3][3] = mtx.a[4][4] = 1;
mtx.a[2][2] = v;
upd (1, 1, n, l, r, mtx);
}
else if (op == 6) {
scanf ("%lld", &v);
matrix mtx;
mtx.n = mtx.m = 4;
mtx.init ();
mtx.a[1][1] = mtx.a[2][2] = mtx.a[4][4] = 1;
mtx.a[4][3] = v;
upd (1, 1, n, l, r, mtx);
}
else if (op == 7) {
matrix res = query (1, 1, n, l, r);
printf ("%lld %lld %lld\n", res.a[1][1], res.a[1][2], res.a[1][3]);
}
}
return 0;
}