线段树每个节点维护(A,B,C,len)向量,操作即是将其乘上一个矩阵。
#include<iostream> #include<cstdio> #include<cmath> #include<cstdlib> #include<cstring> #include<algorithm> using namespace std; #define ll long long #define N 250010 #define P 998244353 char getc(){char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<'0'||c>'9')) c=getchar();return c;} int gcd(int n,int m){return m==0?n:gcd(m,n%m);} int read() { int x=0,f=1;char c=getchar(); while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();} while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar(); return x*f; } int n,m; struct matrix { int n,a[4][4]; matrix operator *(const matrix&b) const { matrix c;c.n=n;memset(c.a,0,sizeof(c.a)); for (int i=0;i<n;i++) for (int k=0;k<4;k++) for (int j=0;j<4;j++) c.a[i][j]=(c.a[i][j]+1ll*a[i][k]*b.a[k][j])%P; return c; } matrix operator +(const matrix&b) const { matrix c;c.n=n;memset(c.a,0,sizeof(c.a)); for (int i=0;i<n;i++) for (int j=0;j<4;j++) c.a[i][j]=(a[i][j]+b.a[i][j])%P; return c; } void print() { cout<<n<<endl; for (int i=0;i<n;i++) { for (int j=0;j<4;j++) cout<<a[i][j]<<' '; cout<<endl; } } }; int L[N<<2],R[N<<2],a[N],b[N],c[N]; bool islazy[N<<2]; matrix tree[N<<2],lazy[N<<2],f,I; void up(int k){tree[k]=tree[k<<1]+tree[k<<1|1];} void build(int k,int l,int r) { L[k]=l,R[k]=r;lazy[k]=I; if (l==r) {tree[k].n=1,tree[k].a[0][0]=a[l],tree[k].a[0][1]=b[l],tree[k].a[0][2]=c[l],tree[k].a[0][3]=1;return;} int mid=l+r>>1; build(k<<1,l,mid); build(k<<1|1,mid+1,r); up(k); } void update(int k,matrix x) { tree[k]=tree[k]*x; lazy[k]=lazy[k]*x; islazy[k]=1; } void down(int k) { update(k<<1,lazy[k]); update(k<<1|1,lazy[k]); lazy[k]=I;islazy[k]=0; } void modify(int k,int l,int r,matrix x) { if (L[k]==l&&R[k]==r) {update(k,x);return;} if (islazy[k]) down(k); int mid=L[k]+R[k]>>1; if (r<=mid) modify(k<<1,l,r,x); else if (l>mid) modify(k<<1|1,l,r,x); else modify(k<<1,l,mid,x),modify(k<<1|1,mid+1,r,x); up(k); } matrix query(int k,int l,int r) { if (L[k]==l&&R[k]==r) return tree[k]; if (islazy[k]) down(k); int mid=L[k]+R[k]>>1; if (r<=mid) return query(k<<1,l,r); else if (l>mid) return query(k<<1|1,l,r); else return query(k<<1,l,mid)+query(k<<1|1,mid+1,r); } signed main() { #ifndef ONLINE_JUDGE freopen("a.in","r",stdin); freopen("a.out","w",stdout); #endif n=read(); for (int i=1;i<=n;i++) a[i]=read(),b[i]=read(),c[i]=read(); I.n=4;for (int i=0;i<4;i++) I.a[i][i]=1; build(1,1,n);f.n=4; m=read(); for (int i=1;i<=m;i++) { int op=read(),l=read(),r=read(); memset(f.a,0,sizeof(f.a)); if (op==1) f.a[0][0]=f.a[1][1]=f.a[2][2]=f.a[3][3]=f.a[1][0]=1; if (op==2) f.a[0][0]=f.a[1][1]=f.a[2][2]=f.a[3][3]=f.a[2][1]=1; if (op==3) f.a[0][0]=f.a[1][1]=f.a[2][2]=f.a[3][3]=f.a[0][2]=1; if (op==4) f.a[0][0]=f.a[1][1]=f.a[2][2]=f.a[3][3]=1,f.a[3][0]=read(); if (op==5) f.a[0][0]=f.a[2][2]=f.a[3][3]=1,f.a[1][1]=read(); if (op==6) f.a[0][0]=f.a[1][1]=f.a[3][3]=1,f.a[3][2]=read(); if (op!=7) modify(1,l,r,f); else { matrix ans=query(1,l,r); printf("%d %d %d ",ans.a[0][0],ans.a[0][1],ans.a[0][2]); } } return 0; //NOTICE LONG LONG!!!!! }