Description

給定序列 $a=(a_1,a_2,?,a_n)$，$b=(b_1,b_2,?,b_n)$ 和 $c=(c_1,c_2,?,c_n)$，有 $m$ 個操作分七種：

• $\mathrm{ex}{\mathrm{c}}_{\mathrm{a}}(l,r)$：對每個 $i\in [l,r]$ 執行 $a_i\leftarrow a_i+b_i$.
• $\mathrm{ex}{\mathrm{c}}_{\mathrm{b}}(l,r)$：對每個 $i\in [l,r]$ 執行 $b_i\leftarrow b_i+c_i$.
• $\mathrm{ex}{\mathrm{c}}_{\mathrm{c}}(l,r)$：對每個 $i\in [l,r]$ 執行 $c_i\leftarrow c_i+a_i$.
• $\mathrm{add}(l,r,v)$：對每個 $i\in [l,r]$ 執行 $a_i\leftarrow a_i+v$.
• $\mathrm{mul}(l,r,v)$：對每個 $i\in [l,r]$ 執行 $b_i\leftarrow b_i\times v$.
• $\mathrm{assign}(l,r,v)$：對每個 $i\in [l,r]$ 執行 $c_i\leftarrow v$.
• $\mathrm{query}(l,r)$：求 $\sum _{i=l}^r{a}_i$，$\sum _{i=l}^r{b}_i$ 和 $\sum _{i=l}^r{c}_i$的值，對 $998244353$ 取模.

Limitations

$1\le n,m\le 2.5\times 10^5$
$0\le a_i,b_i,c_i,v<998244353$
$1\le l\le r\le n$
$5\text{s},500\text{MB}$

Solution

顯然需要矩陣，由于要加常數，每個節點維護矩陣 $\left[\begin{array}{c}a,b,c,1\end{array}\right]$.
然后考慮用矩陣表達修改，由左行右列的口訣，顯然有：

• $\left[\begin{array}{c}a,b,c,1\end{array}\right]\times \left[\begin{array}{c}1,0,0,0\\ 1,1,0,0\\ 0,0,1,0\\ 0,0,0,1\end{array}\right]=\left[\begin{array}{c}a+b,b,c,1\end{array}\right]$
• $\left[\begin{array}{c}a,b,c,1\end{array}\right]\times \left[\begin{array}{c}1,0,0,0\\ 0,1,0,0\\ 0,1,1,0\\ 0,0,0,1\end{array}\right]=\left[\begin{array}{c}a,b+c,c,1\end{array}\right]$
• $\left[\begin{array}{c}a,b,c,1\end{array}\right]\times \left[\begin{array}{c}1,0,1,0\\ 0,1,0,0\\ 0,0,1,0\\ 0,0,0,1\end{array}\right]=\left[\begin{array}{c}a,b,c+a,1\end{array}\right]$
• $\left[\begin{array}{c}a,b,c,1\end{array}\right]\times \left[\begin{array}{c}1,0,0,0\\ 0,1,0,0\\ 0,0,1,0\\ v,0,0,1\end{array}\right]=\left[\begin{array}{c}a+v,b,c,1\end{array}\right]$
• $\left[\begin{array}{c}a,b,c,1\end{array}\right]\times \left[\begin{array}{c}1,0,0,0\\ 0,v,0,0\\ 0,0,1,0\\ 0,0,0,1\end{array}\right]=\left[\begin{array}{c}a,b\times v,c,1\end{array}\right]$
• $\left[\begin{array}{c}a,b,c,1\end{array}\right]\times \left[\begin{array}{c}1,0,0,0\\ 0,1,0,0\\ 0,0,0,0\\ 0,0,v,1\end{array}\right]=\left[\begin{array}{c}a,b,v,1\end{array}\right]$

由于矩陣乘法滿足結合律，可以用線段樹維護，維護每個節點的矩陣與標記（也是一個矩陣），修改操作直接乘上對應矩陣，查詢操作求矩陣和即可.

需要注意幾點：

• 要初始化為單位矩陣的地方，不要忘記初始化.
• 矩陣乘法時，不計算一直為 $0$ 的位置.
• 如果是單位矩陣就不下傳.

Code

$3.85\text{KB},27.95\text{s},80.72\text{MB}\text{(in?total,?C++20?with?O2)}$

#include <bits/stdc++.h>
using namespace std;using i64 = long long;
using ui64 = unsigned long long;
using i128 = __int128;
using ui128 = unsigned __int128;
using f4 = float;
using f8 = double;
using f16 = long double;template<class T>
bool chmax(T &a, const T &b){if(a < b){ a = b; return true; }return false;
}template<class T>
bool chmin(T &a, const T &b){if(a > b){ a = b; return true; }return false;
}constexpr int mod = 998244353;
inline int add(int x, int y) {return x + y >= mod ? x + y - mod : x + y; }
namespace matrix {struct Mat {int mat[4][4];inline Mat(int _e = 1) { memset(mat, 0, sizeof mat); mat[0][0] = mat[1][1] = mat[2][2] = mat[3][3] = _e;}inline int* operator[](int i) { return mat[i]; }inline const int* operator[](int i) const { return mat[i]; }};inline Mat operator+(const Mat& x, const Mat& y) {Mat z(0);for (int i = 0; i < 4; i++)for (int j = 0; j < 4; j++) z[i][j] = add(x[i][j], y[i][j]);return z;}inline Mat operator*(const Mat& x, const Mat& y) {Mat z(0);for (int i = 0; i < 4; i++)for (int k = 0; k < 4; k++) {if (!x[i][k]) continue;for (int j = 0; j < 4; j++) {if (!y[k][j]) continue;z[i][j] = (z[i][j] + 1LL * x[i][k] * y[k][j]) % mod;}}return z;}inline bool operator==(const Mat& x, const Mat& y) {for (int i = 0; i < 4; i++)for (int j = 0; j < 4; j++)if (x[i][j] != y[i][j]) return false;return true;}
}
using matrix::Mat;namespace seg_tree {struct Node {int l, r;Mat val, tag;};inline int ls(int u) { return 2 * u + 1; }inline int rs(int u) { return 2 * u + 2; }struct SegTree {vector<Node> tr;inline SegTree() {}inline SegTree(const vector<Mat>& a) {const int n = a.size();tr.resize(n << 1);build(0, 0, n - 1, a);}inline void pushup(int u, int mid) {tr[u].val = tr[ls(mid)].val + tr[rs(mid)].val;}inline void apply(int u, const Mat& mat) {tr[u].val = tr[u].val * mat;tr[u].tag = tr[u].tag * mat;}inline void pushdown(int u, int mid) {if (tr[u].tag == Mat()) return;apply(ls(mid), tr[u].tag);apply(rs(mid), tr[u].tag);tr[u].tag = Mat();}inline void build(int u, int l, int r, const vector<Mat>& a) {tr[u].l = l, tr[u].r = r;if (l == r) {tr[u].val = a[l];return;}const int mid = (l + r) >> 1;build(ls(mid), l, mid, a);build(rs(mid), mid + 1, r, a);pushup(u, mid);}inline void modify(int u, int l, int r, const Mat& mat) {if (l <= tr[u].l && tr[u].r <= r) return apply(u, mat);const int mid = (tr[u].l + tr[u].r) >> 1;pushdown(u, mid);if (l <= mid) modify(ls(mid), l, r, mat);if (r > mid) modify(rs(mid), l, r, mat);pushup(u, mid); }inline Mat query(int u, int l, int r) {if (l <= tr[u].l && tr[u].r <= r) return tr[u].val;const int mid = (tr[u].l + tr[u].r) >> 1;Mat res = Mat(0);pushdown(u, mid);if (l <= mid) res = res + query(ls(mid), l, r);if (r > mid) res = res + query(rs(mid), l, r);return res;}};
}
using seg_tree::SegTree;signed main() {ios::sync_with_stdio(0);cin.tie(0), cout.tie(0);int n; scanf("%d", &n);vector<Mat> a(n);for (int i = 0; i < n; i++) {scanf("%d %d %d", &a[i][0][0], &a[i][0][1], &a[i][0][2]);a[i][0][3] = 1;}SegTree sgt(a);int m; scanf("%d", &m);for (int i = 0, op, l, r; i < m; i++) {scanf("%d %d %d", &op, &l, &r), l--, r--;if (op == 7) {auto mat = sgt.query(0, l, r);printf("%d %d %d\n", mat[0][0], mat[0][1], mat[0][2]);}else {auto mat = Mat();if (op == 1) mat[1][0] = 1;if (op == 2) mat[2][1] = 1;if (op == 3) mat[0][2] = 1;if (op == 4) scanf("%d", &mat[3][0]);if (op == 5) scanf("%d", &mat[1][1]);if (op == 6) scanf("%d", &mat[3][2]), mat[2][2] = 0;sgt.modify(0, l, r, mat);}}return 0;
}