THUSCH2017] 大魔法师
题目描述
大魔法师小 L 制作了 $n$ 个魔力水晶球，每个水晶球有水、火、土三个属性的能量值。小 L 把这 $n$ 个水晶球在地上从前向后排成一行，然后开始今天的魔法表演。
我们用 $A_i,B_i,C_i$ 分别表示从前向后第 $i$ 个水晶球（下标从 $1$ 开始）的水、火、土的能量值。
小 L 计划施展 $m$ 次魔法。每次，他会选择一个区间 $[l,r]$，然后施展以下 $3$ 大类、$7$ 种魔法之一：
- 魔力激发：令区间里每个水晶球中特定属性的能量爆发，从而使另一个特定属性的能量增强。具体来说，有以下三种可能的表现形式：
- 火元素激发水元素能量：令 $A_i=A_i+B_i$。
- 土元素激发火元素能量：令 $B_i=B_i+C_i$。
- 水元素激发土元素能量：令 $C_i=C_i+A_i$。
- 魔力增强：小 L 挥舞法杖，消耗自身 $v$ 点法力值，来改变区间里每个水晶球的**特定属性**的能量。具体来说，有以下三种可能的表现形式：
- 火元素能量定值增强：令 $A_i=A_i+v$。
- 水元素能量翻倍增强：令 $B_i=B_i\times v$。
- 土元素能量吸收融合：令 $C_i=v$。
- 魔力释放：小 L 将区间里所有水晶球的能量聚集在一起，融合成一个新的水晶球，然后送给场外观众。生成的水晶球每种属性的能量值等于区间内所有水晶球对应能量值的代数和。需要注意的是，魔力释放的过程不会真正改变区间内水晶球的能量。
值得一提的是，小 L 制造和融合的水晶球的原材料都是定制版的 OI 工厂水晶，所以这些水晶球有一个能量阈值 $998244353$。当水晶球中某种属性的能量值大于等于这个阈值时，能量值会自动对阈值取模，从而避免水晶球爆炸。
小 W 为小 L（唯一的）观众，围观了整个表演，并且收到了小 L 在表演中融合的每个水晶球。小 W 想知道，这些水晶球蕴涵的三种属性的能量值分别是多少。
输入格式
从标准输入读入数据。
我们将上述的 $7$ 种魔法，从上到下依次标号为 $1\sim7$。
输入的第一行包含一个整数 $n$（$1\le n\le 2.5\times 10^5$），表示水晶球个数。
接下来 $n$ 行，每行空格隔开的 $3$ 个整数，其中第 $i$ 行的三个数依次表示 $A_i,B_i,C_i$。
接下来一行包含一个整数 $m$（$1\le m\le2.5\times 10^5$），表示施展魔法的次数。
接下来 $m$ 行，每行 $3$ 或 $4$ 个数，格式为 opt l r (v)。其中 opt 表示魔法的编号，$l,r$ 表示施展魔法的区间（保证有 $l\le r$）。特别地，如果施展 $4\sim6$ 号魔法（魔力增强），则还有一个整数 $v$，表示小 L 消耗的法力值。
输出格式
输出到标准输出。
对每个 $7$ 号魔法（魔力释放），输出一行、空格隔开的 $3$ 个整数 `a b c`，分别表示此次融合得到的水晶球的水、火、土元素能量值。
样例 #1
样例输入 #1
2
2 3 3
6 6 6
4
7 1 2
1 1 2
4 1 2 3
7 1 2样例输出 #1
8 9 9
23 9 9
提示
$100\%$ 的数据，$n,m\le2.5\times 10^5,0\le A_i,B_i,C_i,v<998244353$
- $10\%$ 的数据，$n\times m\le10^7$。
- 另外 $10\%$ 的数据，每次魔法的区间均为 $[1,n]$。
- 另外 $10\%$ 的数据，每次非询问魔法的影响区间均为 $[1,n]$，所有修改在询问之前。
- 另外 $10\%$ 的数据，$\operatorname{opt}\in\{4,5,6,7\}$。
- 另外 $15\%$ 的数据，$\operatorname{opt}\in\{1,2,7\}$。
- 另外 $15\%$ 的数据，$\operatorname{opt}\in\{1,2,3,5,7\}$。
- 另外 $15\%$ 的数据，$n,m\le 10^5$。
- 其他数据，无特殊约定。
样例解释
以下展示每次施展魔法后，两个水晶球内的能量：
(2, 3, 3) (6, 6, 6)
(5, 3, 3) (12, 6, 6)
(8, 3, 3) (15, 6, 6)
(8, 3, 3) (15, 6, 6)
解题思路
显然线段树需要分别维护区间内 $a_i$，$b_i$，$c_i$ 的总和，如果只有第 $4 \sim 6$ 种修改操作显然带懒标记的区间修改是可以做的，但对于第 $1 \sim 3$ 种操作每次修改的值都会依赖另外一个变量，就不容易用区间修改加懒标记去维护，除非强制改成单点修改。这时候就可以考虑用矩阵去维护变量了，修改操作就相当于右乘上一个转移矩阵。
定义 $f_i = \begin{bmatrix} a_i & b_i & c_i & 1 \end{bmatrix}$ 表示第 $i$ 个水晶球对应的矩阵。接下来分析每种操作对应的转移矩阵是什么。
对于第 $1$ 种操作，修改后矩阵应该变成 $f_i' = \begin{bmatrix} a_i + b_i & b_i & c_i & 1 \end{bmatrix}$，对应的转移矩阵为 $A_1 = \begin{bmatrix} 1 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{bmatrix}$，那么就会有 $f_i \times A_1 = f_i'$。
对于第 $2$ 种操作，修改后矩阵应该变成 $f_i' = \begin{bmatrix} a_i & b_i + c_i & c_i & 1 \end{bmatrix}$，对应的转移矩阵为 $A_2 = \begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 1 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{bmatrix}$，那么就会有 $f_i \times A_2 = f_i'$。
对于第 $3$ 种操作，修改后矩阵应该变成 $f_i' = \begin{bmatrix} a_i & b_i & c_i + a_i & 1 \end{bmatrix}$，对应的转移矩阵为 $A_3 = \begin{bmatrix} 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{bmatrix}$，那么就会有 $f_i \times A_3 = f_i'$。
对于第 $4$ 种操作，修改后矩阵应该变成 $f_i' = \begin{bmatrix} a_i + v & b_i & c_i & 1 \end{bmatrix}$，对应的转移矩阵为 $A_4 = \begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ v & 0 & 0 & 1 \end{bmatrix}$，那么就会有 $f_i \times A_4 = f_i'$。
对于第 $5$ 种操作，修改后矩阵应该变成 $f_i' = \begin{bmatrix} a_i & b_i \cdot v & c_i & 1 \end{bmatrix}$，对应的转移矩阵为 $A_5 = \begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & v & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{bmatrix}$，那么就会有 $f_i \times A_5 = f_i'$。
对于第 $6$ 种操作，修改后矩阵应该变成 $f_i' = \begin{bmatrix} a_i & b_i & v & 1 \end{bmatrix}$，对应的转移矩阵为 $A_6 = \begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & v & 1 \end{bmatrix}$，那么就会有 $f_i \times A_6 = f_i'$。
因此线段树维护的是区间内矩阵的和，由于矩阵乘法具有分配律，每次修改操作相当于给区间乘上对应的转移矩阵。懒标记自然维护的就是矩阵的累乘，初始化为单位矩阵 $A_0 = \begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{bmatrix}$。
然后就是经典卡常了，只需在矩阵乘法中减少取模运算即可，具体见代码。
AC 代码如下，时间复杂度为 $O(n + m \log{n})$：
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 250010, mod = 998244353;
int a[N], b[N], c[N];
struct Matrix {
array<array<int, 4>, 4> a;
Matrix(array<array<int, 4>, 4> b = {0}) {
a = b;
}
auto& operator[](int x) {
return a[x];
}
Matrix operator+(Matrix b) {
Matrix c;
for (int i = 0; i < 4; i++) {
for (int j = 0; j < 4; j++) {
c[i][j] = (a[i][j] + b[i][j]) % mod;
}
}
return c;
}
Matrix operator*(Matrix b) {
Matrix c;
for (int i = 0; i < 4; i++) {
for (int j = 0; j < 4; j++) {
// 直接一次求出c[i][j]的结果再取模
c[i][j] = ((LL)a[i][0] * b[0][j] + (LL)a[i][1] * b[1][j] + (LL)a[i][2] * b[2][j] + (LL)a[i][3] * b[3][j]) % mod;
}
}
return c;
}
bool operator==(Matrix &b) {
for (int i = 0; i < 4; i++) {
for (int j = 0; j < 4; j++) {
if (a[i][j] != b[i][j]) return false;
}
}
return true;
}
}g[7];
struct Node {
int l, r;
Matrix p, f;
}tr[N * 4];
void build(int u, int l, int r) {
tr[u] = {l, r, g[0]};
if (l == r) {
tr[u].f = Matrix({a[l], b[l], c[l], 1});
}
else {
int mid = l + r >> 1;
build(u << 1, l, mid);
build(u << 1 | 1, mid + 1, r);
tr[u].f = tr[u << 1].f + tr[u << 1 | 1].f;
}
}
void pushdown(int u) {
if (tr[u].f == g[0]) return;
tr[u << 1].f = tr[u << 1].f * tr[u].p;
tr[u << 1].p = tr[u << 1].p * tr[u].p;
tr[u << 1 | 1].f = tr[u << 1 | 1].f * tr[u].p;
tr[u << 1 | 1].p = tr[u << 1 | 1].p * tr[u].p;
tr[u].p = g[0];
}
void modify(int u, int l, int r, Matrix &a) {
if (tr[u].l >= l && tr[u].r <= r) {
tr[u].f = tr[u].f * a;
tr[u].p = tr[u].p * a;
}
else {
pushdown(u);
int mid = tr[u].l + tr[u].r >> 1;
if (l <= mid) modify(u << 1, l, r, a);
if (r >= mid + 1) modify(u << 1 | 1, l, r, a);
tr[u].f = tr[u << 1].f + tr[u << 1 | 1].f;
}
}
Matrix query(int u, int l, int r) {
if (tr[u].l >= l && tr[u].r <= r) return tr[u].f;
pushdown(u);
int mid = tr[u].l + tr[u].r >> 1;
Matrix ret;
if (l <= mid) ret = query(u << 1, l, r);
if (r >= mid + 1) ret = ret + query(u << 1 | 1, l, r);
return ret;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i] >> b[i] >> c[i];
}
g[0] = Matrix({1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1}); // 单位矩阵
g[1] = Matrix({1, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1}); // 操作1对应的转移矩阵
g[2] = Matrix({1, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1}); // 操作2对应的转移矩阵
g[3] = Matrix({1, 0, 1, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1}); // 操作3对应的转移矩阵
g[4] = Matrix({1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1}); // 操作4对应的转移矩阵
g[5] = Matrix({1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1}); // 操作5对应的转移矩阵
g[6] = Matrix({1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1}); // 操作6对应的转移矩阵
build(1, 1, n);
cin >> m;
while (m--) {
int op, l, r, v;
cin >> op >> l >> r;
if (op < 7) {
if (op > 3) { // 对于操作4~6，需要在转移矩阵相应的位置改成v
cin >> v;
if (op == 4) g[4][3][0] = v;
else if (op == 5) g[5][1][1] = v;
else g[6][3][2] = v;
}
modify(1, l, r, g[op]);
}
else {
Matrix ret = query(1, l, r);
cout << ret[0][0] << ' ' << ret[0][1] << ' ' << ret[0][2] << '\n';
}
}
return 0;
}
参考资料
线段树+矩阵乘法：https://www.luogu.com.cn/article/qf6az4pt
标签：end,Matrix,int,矩阵,魔法师,bmatrix,THUSCH2017,水晶球 From： https://www.cnblogs.com/onlyblues/p/18041967