一个序列，每个物品有三个权值 $A,B,C$
要求维护：
1.区间 $A_i+=B_i$
2.区间 $B_i+=C_i$
3.区间 $C_i+=A_i$
4.区间 $A_i+=v$
5.区间 $B_i imes = v$
6.区间 $C_i = v$
7.询问区间 $A,B,C$ 各自的和
线段树，每个点维护 $A,B,C,区间长度$
每次修改相当于区间乘一个转移矩阵
时间复杂度 $O(16nlogn)$
垫底
#include <bits/stdc++.h> #define LL long long using namespace std; #define rep(i, s, t) for (register int i = (s), i##end = (t); i <= i##end; ++i) #define dwn(i, s, t) for (register int i = (s), i##end = (t); i >= i##end; --i) inline int read() { int x = 0, f = 1; char ch = getchar(); for (; !isdigit(ch); ch = getchar())if (ch == '-')f = -f; for (; isdigit(ch); ch = getchar()) x = 10 * x + ch - '0'; return x * f; } const int mod = 998244353, maxn = 2.5e5 + 10; #define ls (x << 1) #define rs ((x << 1) | 1) int n, q, A[maxn], B[maxn], C[maxn]; struct Matrix { int a[4][4]; Matrix() {memset(a, 0, sizeof(a));} Matrix operator * (const Matrix &b) const { Matrix c; rep(i, 0, 3) rep(j, 0, 3) rep(k, 0, 3) (c.a[i][j] += (1LL * a[i][k] * b.a[k][j] % mod)) %= mod; return c; } Matrix operator + (const Matrix &b) const { Matrix c; rep(i, 0, 3) rep(j, 0, 3) c.a[i][j] = (a[i][j] + b.a[i][j]) % mod; return c; } }tag[maxn << 2]; int seg[maxn << 2][4]; void mul(int *f, Matrix gg) { int tmp[4] = {0, 0, 0, 0}; rep(i, 0, 3) rep(j, 0, 3) (tmp[j] += (1LL * f[i] * gg.a[i][j] % mod)) %= mod; rep(i, 0, 3) f[i] = tmp[i]; } inline int clear(Matrix x) { if (!(x.a[0][0] == 1 && x.a[1][1] == 1 && x.a[2][2] == 1 && x.a[3][3] == 1))return false; if (x.a[0][1] || x.a[0][2] || x.a[0][3] || x.a[1][0] || x.a[1][2] || x.a[1][3])return false; if (x.a[2][0] || x.a[2][1] || x.a[2][3] || x.a[3][0] || x.a[3][1] || x.a[3][2]) return false; return true; } inline void pushup(int x) { rep(i, 0, 3) seg[x][i] = (seg[ls][i] + seg[rs][i]) % mod; } inline void pushdown(int x) { if(clear(tag[x])) return; tag[ls] = tag[ls] * tag[x], tag[rs] = tag[rs] * tag[x]; mul(seg[ls], tag[x]), mul(seg[rs], tag[x]); rep(i, 0, 3) rep(j, 0, 3) tag[x].a[i][j] = (i == j); } inline void build(int x, int l, int r) { if(l == r) { seg[x][0] = A[l]; seg[x][1] = B[l]; seg[x][2] = C[l]; seg[x][3] = 1; return; } int mid = (l + r) >> 1; build(ls, l, mid); build(rs, mid + 1, r); pushup(x); } Matrix cur; int res[4]; inline void update(int x, int l, int r, int L, int R) { if(L <= l && r <= R) { mul(seg[x], cur); tag[x] = tag[x] * cur; return; } pushdown(x); int mid = (l + r) >> 1; if(L <= mid) update(ls, l, mid, L, R); if(R > mid) update(rs, mid + 1, r, L, R); pushup(x); } inline void query(int x, int l, int r, int L, int R) { if(L <= l && r <= R) { rep(i, 0, 3) (res[i] += seg[x][i]) %= mod; return; } pushdown(x); int mid = (l + r) >> 1; if(L <= mid) query(ls, l, mid, L, R); if(R > mid) query(rs, mid + 1, r, L, R); } int main() { n = read(); rep(i, 1, (n<<2)) rep(j, 0, 3) rep(k, 0, 3) tag[i].a[j][k] = (j == k); rep(i, 1, n) A[i] = read(), B[i] = read(), C[i] = read(); build(1, 1, n); q = read(); while(q--) { int opt = read(), l = read(), r = read(); rep(i, 0, 3) rep(j, 0, 3) cur.a[i][j] = (i == j); if(opt == 1) cur.a[1][0]++; else if(opt == 2) cur.a[2][1]++; else if(opt == 3) cur.a[0][2]++; else if(opt == 4) (cur.a[3][0] += read()) %= mod; else if(opt == 5) cur.a[1][1] = read(); else if(opt == 6) cur.a[2][2] = 0, cur.a[3][2] = read(); if(opt != 7) update(1, 1, n, l, r); if(opt == 7) { rep(i, 0, 3) res[i] = 0; query(1, 1, n, l, r); printf("%d %d %d ", res[0], res[1], res[2]); continue; } } }