（有任何问题欢迎留言或私聊 && 欢迎交流讨论哦
Catalog
@
Problem：传送门
Portal
原题目描述在最下面。
简单的说，每个点是一个矩阵，区间赋值和区间求积。
Solution：
(div2)版本就(O(n*m*9))暴力更新暴力矩阵乘法求答案就行了，代码挺短的，有需要的话去另一篇博客里有代码。
(div1)题解就上面这个，相信大家看完应该都能(ac)。
本题只有两种操作，区间赋值和区间求和(矩阵的积)。很自然就想到要用线段树优化咯，然后线段树每个节点都是一个矩阵。
但是这题要先把区间长度扩展为2的幂次，为什么呢？因为：
长度为(n)的区间长度有大概(log(n))种，但是当(n)不是(2)的幂次的时候，各种区间的长度是没有规律的。
这题线段树每个节点维护的是矩阵信息，用(lazy)标记优化区间赋值时，其实就是求矩阵的(k)次幂。
因为会有很多区间的长度相同，可以先把矩阵的k次幂预处理出来。
而只有当总长度是2的幂次时，每个节点覆盖的区间长度都会是2的幂次。这样就解释完了。
理解了这个，这题就随便写了。
AC_Code：
//哇，这题ac完感觉好爽啊
//第一次写这种结构体线段树还重载操作符的，海星
//没有人写博客，只能看着官方题解意会解法
#include<bits/stdc++.h>
#define clr(a, b) memset(a,b,sizeof((a)))
#define lson rt<<1
#define rson rt<<1|1
using namespace std;
typedef long long LL;
const int MXN = 2e5 + 7;
const LL mod = 998244353;
int n, m, Q;
int ar[MXN][3][3], two[33];
int lazy[MXN<<2][3][3], flag[MXN<<2];
map<int, int> mp;
struct edge {
int opt, l, r;
int ar[3][3];
}node[MXN];
struct lp {
int sum[3][3];
friend lp operator *(const lp&a, const lp&b) {
lp c;
clr(c.sum, 0);
for(int k = 0; k < 3; ++k) for(int i = 0; i < 3; ++i) for(int j = 0; j < 3; ++j) {
c.sum[i][j] = (c.sum[i][j]+(LL)a.sum[i][k]*b.sum[k][j])%mod;
}
return c;
}
}cw[MXN<<2], tp[MXN][33];
void push_up(int rt) {
cw[rt] = cw[lson] * cw[rson];
}
void build(int l,int r,int rt) {
flag[rt] = -1;
if(l == r) {
for(int i = 0; i < 3; ++i) for(int j = 0; j < 3; ++j) cw[rt].sum[i][j] = ar[l][i][j];
return ;
}
int mid = (l + r) >> 1;
build(l, mid, lson); build(mid+1,r,rson);
push_up(rt);
}
void push_down(int l,int mid,int r,int rt) {
if(flag[rt] == -1) return;
flag[lson] = flag[rson] = flag[rt];
for(int i = 0; i < 3; ++i) for(int j = 0; j < 3; ++j) lazy[lson][i][j] = lazy[rt][i][j], lazy[rson][i][j] = lazy[rt][i][j];
cw[lson] = tp[flag[rt]][mp[mid-l+1]-1];
cw[rson] = tp[flag[rt]][mp[r-mid]-1];
assert(mp[mid-l+1]); assert(mp[r-mid]);
flag[rt] = -1;
}
void update(int L,int R,int id,int l,int r,int rt) {
if(L <= l && r <= R) {
flag[rt] = id;
for(int i = 0; i < 3; ++i) for(int j = 0; j < 3; ++j) lazy[rt][i][j] = node[id].ar[i][j];
assert(mp[r-l+1]);
cw[rt] = tp[id][mp[r-l+1]-1];
return ;
}
int mid = (l + r) >> 1;
push_down(l, mid, r, rt);
if(L > mid) update(L, R, id, mid+1, r, rson);
else if(R <= mid) update(L, R, id, l, mid, lson);
else {
update(L,mid,id,l,mid,lson); update(mid+1,R,id,mid+1,r,rson);
}
push_up(rt);
}
lp query(int L,int R,int l,int r,int rt) {
if(L <= l && r <= R) {
return cw[rt];
}
int mid = (l + r) >> 1;
push_down(l, mid, r, rt);
if(L > mid) return query(L, R, mid+1, r, rson);
else if(R <= mid) return query(L, R, l, mid, lson);
else {
return query(L,mid,l,mid,lson)*query(mid+1,R,mid+1,r,rson);
}
}
int main() {
two[0] = 1, mp[1] = 1;
for(int i = 1; i <= 17; ++i) two[i] = two[i-1] << 1, mp[1<<i] = i + 1;
scanf("%d%d", &n, &Q);
for(int i = 1; i < n; ++i) {
for(int j = 0; j < 3; ++j) for(int k = 0; k < 3; ++k) scanf("%d", &ar[i][j][k]);
}
m = 2;
while(m < n) m <<= 1;
build(1, m, 1);
int opt, l, r;
for(int i = 1; i <= Q; ++i) {
scanf("%d%d%d", &node[i].opt, &node[i].l, &node[i].r);
if(node[i].opt == 1) {
for(int k = 0; k < 3; ++k) for(int j = 0; j < 3; ++j) {
scanf("%d", &node[i].ar[k][j]);
tp[i][0].sum[k][j] = node[i].ar[k][j];
}
for(int k = 1; k <= 17; ++k) {
tp[i][k] = tp[i][k-1] * tp[i][k-1];
}
update(node[i].l, node[i].r, i, 1, m, 1);
}else {
LL ans = 0;
lp a = query(node[i].l, node[i].r-1, 1, m, 1);
for(int i = 0; i < 3; ++i) for(int j = 0; j < 3; ++j) ans = (ans + a.sum[i][j]) % mod;
printf("%lld
", ans);
}
}
return 0;
}
Problem Description：
