链接
分析
因为每个点维护的三个值会互相影响，所以不能分别写 tag，但我们发现其实所有操作都可以用矩阵来描述，所以你只需要在线段树上维护一个矩阵lazytag和四个区间和，分别是 \(\sum a,\sum b,\sum c,\sum 1\)。
同时我们发现对于一次覆盖区间的修改，我们只需要用修改矩阵乘上 lazytag 和这个四个区间和组成的 \(1\times 4\) 向量。所以就可以做到 \(O(4^2 n\log n)\) 了。注意矩阵的左乘右乘要分清楚。
然后这题稍微有一点卡常，你可以把矩乘的最里面一层拆开，另外可以不开long long，只在乘的时候强转一下。
code
点击查看代码
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define in read()
inline char nc(){
static char buf[100000],*p1=buf,*p2=buf;
return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline int read(){
char ch=nc();int sum=0;
while(!isdigit(ch))ch=nc();
while(isdigit(ch))sum=sum*10+ch-48,ch=nc();
return sum;
}
const int mod=998244353;
const int N=250005;
inline int add(int x,int y){int z=x+y;return z>=mod?z-mod:z;}
inline void Add(int &x,int y){x=add(x,y);}
inline int mul(int x,int y){ll z=(ll)x*y;return z>=mod?z%mod:z;}
inline void Mul(int &x,int y){x=mul(x,y);}
struct mat{
int a[4][4];
mat(){for(int i=0;i<=3;i++)for(int j=0;j<=3;j++)a[i][j]=0;}
friend void I(mat &a){for(int i=0;i<=3;i++)for(int j=0;j<=3;j++)a.a[i][j]=(i==j);}
friend mat operator*(const mat &a,const mat &b){
mat c;
for(int i=0;i<=3;i++)
for(int k=0,tmp;k<=3;k++){
tmp=a.a[i][k];
Add(c.a[i][0],mul(tmp,b.a[k][0]));
Add(c.a[i][1],mul(tmp,b.a[k][1]));
Add(c.a[i][2],mul(tmp,b.a[k][2]));
Add(c.a[i][3],mul(tmp,b.a[k][3]));
}
return c;
}
}T[N<<2],opt1,opt2,opt3,opt4,opt5,opt6;
int n,m,a[N],b[N],c[N];
int vis[N<<2];
inline void pro(){
opt1.a[0][0]=1,opt1.a[0][1]=0,opt1.a[0][2]=0,opt1.a[0][3]=0,
opt1.a[1][0]=0,opt1.a[1][1]=1,opt1.a[1][2]=0,opt1.a[1][3]=0,
opt1.a[2][0]=0,opt1.a[2][1]=0,opt1.a[2][2]=1,opt1.a[2][3]=0,
opt1.a[3][0]=0,opt1.a[3][1]=0,opt1.a[3][2]=0,opt1.a[3][3]=1;
opt6=opt5=opt4=opt3=opt2=opt1;
opt1.a[0][1]=1,opt2.a[1][2]=1,
opt3.a[2][0]=1,opt6.a[2][2]=0;
}
int sa[N<<2],sb[N<<2],sc[N<<2],sd[N<<2];
inline void pushup(int p){
sa[p]=add(sa[p<<1],sa[p<<1|1]),
sb[p]=add(sb[p<<1],sb[p<<1|1]),
sc[p]=add(sc[p<<1],sc[p<<1|1]),
sd[p]=add(sd[p<<1],sd[p<<1|1]);
}
inline void f(int p,mat d){
T[p]=d*T[p];
int ta,tb,tc,td;
ta=add(add(mul(d.a[0][0],sa[p]),mul(d.a[0][1],sb[p])),add(mul(d.a[0][2],sc[p]),mul(d.a[0][3],sd[p]))),
tb=add(add(mul(d.a[1][0],sa[p]),mul(d.a[1][1],sb[p])),add(mul(d.a[1][2],sc[p]),mul(d.a[1][3],sd[p]))),
tc=add(add(mul(d.a[2][0],sa[p]),mul(d.a[2][1],sb[p])),add(mul(d.a[2][2],sc[p]),mul(d.a[2][3],sd[p]))),
td=add(add(mul(d.a[3][0],sa[p]),mul(d.a[3][1],sb[p])),add(mul(d.a[3][2],sc[p]),mul(d.a[3][3],sd[p])));
sa[p]=ta,sb[p]=tb,sc[p]=tc,sd[p]=td;
vis[p]=1;
}
inline void pushdown(int p){
if(vis[p])f(p<<1,T[p]),f(p<<1|1,T[p]),I(T[p]),vis[p]=0;
}
inline void built(int l,int r,int p){
I(T[p]);
if(l==r){sa[p]=a[l],sb[p]=b[l],sc[p]=c[l],sd[p]=1;return ;}
int mid=(l+r)>>1;
built(l,mid,p<<1);
built(mid+1,r,p<<1|1);
pushup(p);
}
inline void change(int l,int r,int p,int ql,int qr,mat d){
vis[p]=1;
if(l>=ql&&r<=qr){f(p,d);return ;}
int mid=(l+r)>>1;pushdown(p);
if(ql<=mid)change(l,mid,p<<1,ql,qr,d);
if(qr>mid)change(mid+1,r,p<<1|1,ql,qr,d);
pushup(p);
}
struct llmmkk{
int a,b,c;
void operator+=(const llmmkk &y)
{Add(a,y.a),Add(b,y.b),Add(c,y.c);}
};
inline llmmkk query(int l,int r,int p,int ql,int qr){
if(l>=ql&&r<=qr)return {sa[p],sb[p],sc[p]};
int mid=(l+r)>>1;pushdown(p);llmmkk res={0,0,0};
if(ql<=mid)res+=query(l,mid,p<<1,ql,qr);
if(qr>mid)res+=query(mid+1,r,p<<1|1,ql,qr);
return res;
}
signed main(){
n=in;
for(int i=1;i<=n;i++)
a[i]=in,b[i]=in,c[i]=in;
built(1,n,1),m=in,pro();
for(int i=1,opt,l,r;i<=m;i++){
opt=in,l=in,r=in;
if(opt==1)change(1,n,1,l,r,opt1);
else if(opt==2)change(1,n,1,l,r,opt2);
else if(opt==3)change(1,n,1,l,r,opt3);
else if(opt==4)opt4.a[0][3]=in,change(1,n,1,l,r,opt4);
else if(opt==5)opt5.a[1][1]=in,change(1,n,1,l,r,opt5);
else if(opt==6)opt6.a[2][3]=in,change(1,n,1,l,r,opt6);
else{
llmmkk ans=query(1,n,1,l,r);
cout<<ans.a<<' '<<ans.b<<' '<<ans.c<<'\n';
}
}
return 0;
}