文件详细信息
本文件的大小为 4259 字节。
/*
$$\begin{bmatrix} \sum A_i & \sum B_i & \sum C_i & \sum 1 \end{bmatrix} \times \begin{bmatrix} 1 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{bmatrix} = \begin{bmatrix} (\sum A_i)+(\sum B_i) & \sum B_i & \sum C_i & \sum 1 \end{bmatrix}$$
$$\begin{bmatrix} \sum A_i & \sum B_i & \sum C_i & \sum 1 \end{bmatrix} \times \begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 1 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{bmatrix} = \begin{bmatrix} \sum A_i & (\sum B_i+\sum C_i) & \sum C_i & \sum 1 \end{bmatrix}$$
$$\begin{bmatrix} \sum A_i & \sum B_i & \sum C_i & \sum 1 \end{bmatrix} \times \begin{bmatrix} 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{bmatrix} = \begin{bmatrix} \sum A_i & \sum B_i & (\sum C_i+\sum A_i) & \sum 1 \end{bmatrix}$$
$$\begin{bmatrix} \sum A_i & \sum B_i & \sum C_i & \sum 1 \end{bmatrix} \times \begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ v & 0 & 0 & 1 \end{bmatrix} = \begin{bmatrix} \sum (A_i+v) & \sum B_i & \sum C_i & \sum 1 \end{bmatrix}$$
$$\begin{bmatrix} \sum A_i & \sum B_i & \sum C_i & \sum 1 \end{bmatrix} \times \begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & v & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{bmatrix} = \begin{bmatrix} \sum A_i & \sum (v \times B_i) & \sum C_i & \sum 1 \end{bmatrix}$$
$$\begin{bmatrix} \sum A_i & \sum B_i & \sum C_i & \sum 1 \end{bmatrix} \times \begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & v & 1 \end{bmatrix} = \begin{bmatrix} \sum A_i & \sum B_i & \sum v & \sum 1 \end{bmatrix}$$
*/
#include<cstdio>
#include<cstring>
template<typename T>
void read(T&num){
int ch=getchar();
num=0;
while(ch<48||ch>57)ch=getchar();
while(ch>=48&&ch<=57)num=(num<<3)+(num<<1)+(ch^48),ch=getchar();
}
template<typename T>
void write(T a){
static int ch[20],cnt;
cnt=0;
if(a<0)putchar('-'),a=-a;
if(a==0)putchar('0');
while(a)ch[cnt++]=a%10|48,a/=10;
while(cnt)putchar(ch[--cnt]);
}
typedef long long ll;
const int maxn=250005,sz=4;
const ll P=998244353;
int n,m;
struct Matrix{
ll a[sz][sz];
Matrix(){
memset(a,0,sizeof(a));
}
}I,op[7];
Matrix operator+(const Matrix a,const Matrix b){
Matrix ans;
for(int i=0;i<sz;i++)
for(int j=0;j<sz;j++)
ans.a[i][j]=(a.a[i][j]+b.a[i][j])%P;
return ans;
}
Matrix operator*(const Matrix a,const Matrix b){
Matrix ans;
for(int i=0;i<sz;i++)
for(int j=0;j<sz;j++)
for(int k=0;k<sz;k++)
ans.a[i][j]=(ans.a[i][j]+a.a[i][k]*b.a[k][j])%P;
return ans;
}
struct Seg{
Matrix s,tag;
bool e;//true -> pushdown is needed.
}T[maxn<<2];
void pushup(int u){
T[u].s=T[u<<1].s+T[u<<1|1].s;
}
void pushdown(int u){
if(T[u].e){
int l=u<<1,r=u<<1|1;
T[l].s=T[l].s*T[u].tag;
if(T[l].e)T[l].tag=T[l].tag*T[u].tag;
else{
T[l].tag=T[u].tag;
T[l].e=true;
}
T[r].s=T[r].s*T[u].tag;
if(T[r].e)T[r].tag=T[r].tag*T[u].tag;
else{
T[r].tag=T[u].tag;
T[r].e=true;
}
T[u].e=false;
}
}
void build(int u,int l,int r){
if(l==r){
read(T[u].s.a[0][0]);
read(T[u].s.a[0][1]);
read(T[u].s.a[0][2]);
T[u].s.a[0][3]=1;
return;
}
int m=(l+r)>>1;
build(u<<1,l,m);
build(u<<1|1,m+1,r);
pushup(u);
}
void modify(int u,int l,int r,int ql,int qr,int opt){
if(ql<=l&&r<=qr){
T[u].s=T[u].s*op[opt];
if(T[u].e)T[u].tag=T[u].tag*op[opt];
else{
T[u].tag=op[opt];
T[u].e=true;
}
return;
}
pushdown(u);
int m=(l+r)>>1;
if(ql<=m)modify(u<<1,l,m,ql,qr,opt);
if(qr>m)modify(u<<1|1,m+1,r,ql,qr,opt);
pushup(u);
}
Matrix query(int u,int l,int r,int ql,int qr){
if(ql<=l&&r<=qr)return T[u].s;
pushdown(u);
int m=(l+r)>>1;
if(qr<=m)return query(u<<1,l,m,ql,qr);
if(ql>m)return query(u<<1|1,m+1,r,ql,qr);
return query(u<<1,l,m,ql,qr)+query(u<<1|1,m+1,r,ql,qr);
}
int main(){
for(int i=0;i<sz;i++)I.a[i][i]=1;
for(int s=1;s<=6;s++)op[s]=I;
op[1].a[1][0]=1;
op[2].a[2][1]=1;
op[3].a[0][2]=1;
op[6].a[2][2]=0;
read(n);
build(1,1,n);
read(m);
for(int i=1,opt,l,r,v;i<=m;i++){
read(opt),read(l),read(r);
if(opt<=6){
if(opt>=4)read(v);
if(opt==4)op[4].a[3][0]=v;
else if(opt==5)op[5].a[1][1]=v;
else op[6].a[3][2]=v;
modify(1,1,n,l,r,opt);
}else{
Matrix ans=query(1,1,n,l,r);
write(ans.a[0][0]),putchar(' '),write(ans.a[0][1]),putchar(' '),write(ans.a[0][2]),putchar('\n');
}
}
return 0;
}