分析
在线段树上用(4 imes 4)的矩阵打标记。
代码
#include <bits/stdc++.h>
#define rin(i,a,b) for(register int i=(a);i<=(b);++i)
#define irin(i,a,b) for(register int i=(a);i>=(b);--i)
#define trav(i,a) for(register int i=head[a];i;i=e[i].nxt)
typedef long long LL;
using std::cin;
using std::cout;
using std::endl;
inline int read(){
int x=0,f=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
while(isdigit(ch)){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
const int MAXN=250005;
const LL MOD=998244353;
int n,m,ql,qr;
LL a[MAXN],b[MAXN],c[MAXN];
struct Mat{
LL a[4][4];
Mat(){memset(a,0,sizeof a);}
inline LL* operator [] (int x){return a[x];}
inline friend Mat operator * (Mat x,Mat y){
Mat ret;
ret[0][0]=(ret[0][0]+x[0][0]*y[0][0])%MOD;
ret[0][1]=(ret[0][1]+x[0][0]*y[0][1])%MOD;
ret[0][2]=(ret[0][2]+x[0][0]*y[0][2])%MOD;
ret[0][3]=(ret[0][3]+x[0][0]*y[0][3])%MOD;
ret[0][0]=(ret[0][0]+x[0][1]*y[1][0])%MOD;
ret[0][1]=(ret[0][1]+x[0][1]*y[1][1])%MOD;
ret[0][2]=(ret[0][2]+x[0][1]*y[1][2])%MOD;
ret[0][3]=(ret[0][3]+x[0][1]*y[1][3])%MOD;
ret[0][0]=(ret[0][0]+x[0][2]*y[2][0])%MOD;
ret[0][1]=(ret[0][1]+x[0][2]*y[2][1])%MOD;
ret[0][2]=(ret[0][2]+x[0][2]*y[2][2])%MOD;
ret[0][3]=(ret[0][3]+x[0][2]*y[2][3])%MOD;
ret[0][0]=(ret[0][0]+x[0][3]*y[3][0])%MOD;
ret[0][1]=(ret[0][1]+x[0][3]*y[3][1])%MOD;
ret[0][2]=(ret[0][2]+x[0][3]*y[3][2])%MOD;
ret[0][3]=(ret[0][3]+x[0][3]*y[3][3])%MOD;
ret[1][0]=(ret[1][0]+x[1][0]*y[0][0])%MOD;
ret[1][1]=(ret[1][1]+x[1][0]*y[0][1])%MOD;
ret[1][2]=(ret[1][2]+x[1][0]*y[0][2])%MOD;
ret[1][3]=(ret[1][3]+x[1][0]*y[0][3])%MOD;
ret[1][0]=(ret[1][0]+x[1][1]*y[1][0])%MOD;
ret[1][1]=(ret[1][1]+x[1][1]*y[1][1])%MOD;
ret[1][2]=(ret[1][2]+x[1][1]*y[1][2])%MOD;
ret[1][3]=(ret[1][3]+x[1][1]*y[1][3])%MOD;
ret[1][0]=(ret[1][0]+x[1][2]*y[2][0])%MOD;
ret[1][1]=(ret[1][1]+x[1][2]*y[2][1])%MOD;
ret[1][2]=(ret[1][2]+x[1][2]*y[2][2])%MOD;
ret[1][3]=(ret[1][3]+x[1][2]*y[2][3])%MOD;
ret[1][0]=(ret[1][0]+x[1][3]*y[3][0])%MOD;
ret[1][1]=(ret[1][1]+x[1][3]*y[3][1])%MOD;
ret[1][2]=(ret[1][2]+x[1][3]*y[3][2])%MOD;
ret[1][3]=(ret[1][3]+x[1][3]*y[3][3])%MOD;
ret[2][0]=(ret[2][0]+x[2][0]*y[0][0])%MOD;
ret[2][1]=(ret[2][1]+x[2][0]*y[0][1])%MOD;
ret[2][2]=(ret[2][2]+x[2][0]*y[0][2])%MOD;
ret[2][3]=(ret[2][3]+x[2][0]*y[0][3])%MOD;
ret[2][0]=(ret[2][0]+x[2][1]*y[1][0])%MOD;
ret[2][1]=(ret[2][1]+x[2][1]*y[1][1])%MOD;
ret[2][2]=(ret[2][2]+x[2][1]*y[1][2])%MOD;
ret[2][3]=(ret[2][3]+x[2][1]*y[1][3])%MOD;
ret[2][0]=(ret[2][0]+x[2][2]*y[2][0])%MOD;
ret[2][1]=(ret[2][1]+x[2][2]*y[2][1])%MOD;
ret[2][2]=(ret[2][2]+x[2][2]*y[2][2])%MOD;
ret[2][3]=(ret[2][3]+x[2][2]*y[2][3])%MOD;
ret[2][0]=(ret[2][0]+x[2][3]*y[3][0])%MOD;
ret[2][1]=(ret[2][1]+x[2][3]*y[3][1])%MOD;
ret[2][2]=(ret[2][2]+x[2][3]*y[3][2])%MOD;
ret[2][3]=(ret[2][3]+x[2][3]*y[3][3])%MOD;
ret[3][0]=(ret[3][0]+x[3][0]*y[0][0])%MOD;
ret[3][1]=(ret[3][1]+x[3][0]*y[0][1])%MOD;
ret[3][2]=(ret[3][2]+x[3][0]*y[0][2])%MOD;
ret[3][3]=(ret[3][3]+x[3][0]*y[0][3])%MOD;
ret[3][0]=(ret[3][0]+x[3][1]*y[1][0])%MOD;
ret[3][1]=(ret[3][1]+x[3][1]*y[1][1])%MOD;
ret[3][2]=(ret[3][2]+x[3][1]*y[1][2])%MOD;
ret[3][3]=(ret[3][3]+x[3][1]*y[1][3])%MOD;
ret[3][0]=(ret[3][0]+x[3][2]*y[2][0])%MOD;
ret[3][1]=(ret[3][1]+x[3][2]*y[2][1])%MOD;
ret[3][2]=(ret[3][2]+x[3][2]*y[2][2])%MOD;
ret[3][3]=(ret[3][3]+x[3][2]*y[2][3])%MOD;
ret[3][0]=(ret[3][0]+x[3][3]*y[3][0])%MOD;
ret[3][1]=(ret[3][1]+x[3][3]*y[3][1])%MOD;
ret[3][2]=(ret[3][2]+x[3][3]*y[3][2])%MOD;
ret[3][3]=(ret[3][3]+x[3][3]*y[3][3])%MOD;
return ret;
}
inline friend Mat operator + (Mat x,Mat y){
Mat ret;
ret[0][0]=(x[0][0]+y[0][0])%MOD;
ret[0][1]=(x[0][1]+y[0][1])%MOD;
ret[0][2]=(x[0][2]+y[0][2])%MOD;
ret[0][3]=(x[0][3]+y[0][3])%MOD;
return ret;
}
inline bool check(){
if(a[0][0]!=1||a[1][1]!=1||a[2][2]!=1||a[3][3]!=1) return true;
if(a[0][1]||a[0][2]||a[0][3]||a[1][0]||a[1][2]||a[1][3]||a[2][0]||a[2][1]||a[2][3]||a[3][0]||a[3][1]||a[3][2]) return true;
return false;
}
}unit,optm[4],kk,seg[MAXN<<2],tag[MAXN<<2];
#define mid ((l+r)>>1)
#define lc (o<<1)
#define rc ((o<<1)|1)
inline void pushtag(int o,Mat y){
seg[o]=seg[o]*y;
tag[o]=tag[o]*y;
}
inline void pushdown(int o){
if(!tag[o].check()) return;
pushtag(lc,tag[o]);
pushtag(rc,tag[o]);
tag[o]=unit;
}
void build(int o,int l,int r){
tag[o]=unit;
if(l==r){
seg[o][0][0]=a[l];
seg[o][0][1]=b[l];
seg[o][0][2]=c[l];
seg[o][0][3]=1;
return;
}
build(lc,l,mid);
build(rc,mid+1,r);
seg[o]=seg[lc]+seg[rc];
}
void upd(int o,int l,int r){
if(ql<=l&&r<=qr){pushtag(o,kk);return;}
pushdown(o);
if(mid>=ql) upd(lc,l,mid);
if(mid<qr) upd(rc,mid+1,r);
seg[o]=seg[lc]+seg[rc];
}
Mat query(int o,int l,int r){
if(ql<=l&&r<=qr) return seg[o];
pushdown(o);
if(mid<ql) return query(rc,mid+1,r);
else if(mid>=qr) return query(lc,l,mid);
else return query(lc,l,mid)+query(rc,mid+1,r);
}
#undef mid
#undef lc
#undef rc
int main(){
rin(i,0,3) unit[i][i]=1;
rin(i,1,3) optm[i]=unit;
optm[1][1][0]=1;
optm[2][2][1]=1;
optm[3][0][2]=1;
n=read();
rin(i,1,n) a[i]=read(),b[i]=read(),c[i]=read();
build(1,1,n);
m=read();
while(m--){
int opt=read();ql=read(),qr=read();
if(opt<=3) kk=optm[opt];
else if(opt==4) kk=unit,kk[3][0]=read();
else if(opt==5) kk=unit,kk[1][1]=read();
else if(opt==6) kk=unit,kk[2][2]=0,kk[3][2]=read();
else{
Mat ans=query(1,1,n);
printf("%lld %lld %lld
",ans[0][0],ans[0][1],ans[0][2]);
continue;
}
upd(1,1,n);
}
return 0;
}