题目：https://loj.ac/problem/2980
线段树维护矩阵。
然后是 30 分。似乎是被卡常了？……
#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
#define ls Ls[cr]
#define rs Rs[cr]
using namespace std;
int rdn()
{
int ret=;bool fx=;char ch=getchar();
while(ch>''||ch<''){if(ch=='-')fx=;ch=getchar();}
while(ch>=''&&ch<='')ret=ret*+ch-'',ch=getchar();
return fx?ret:-ret;
}
const int N=2e5+5e4+,M=5e5+,mod=;
int upt(int x){while(x>=mod)x-=mod;while(x<)x+=mod;return x;} int n,m,a[N],b[N],c[N],tot,Ls[M],Rs[M];
struct Mtr{
int a[][];
Mtr(){memset(a,,sizeof a);}
void init(){for(int i=;i<;i++)a[i][i]=;}
Mtr operator* (const Mtr &b)const
{
Mtr c;
for(int i=;i<;i++)
for(int k=;k<;k++)
for(int j=;j<;j++)
c.a[i][j]=(c.a[i][j]+(ll)a[i][k]*b.a[k][j])%mod;
return c;
}
Mtr operator+ (const Mtr &b)const
{
Mtr c=*this;
for(int i=;i<;i++)c.a[][i]=upt(c.a[][i]+b.a[][i]);
return c;
}
bool operator== (const Mtr &b)const
{
for(int i=;i<;i++)
for(int j=;j<;j++)if(a[i][j]!=b.a[i][j])return false;
return true;
}
}Ml[],vl[M],tg[M],I,tp;
void build(int l,int r,int cr)
{
if(l==r)
{
vl[cr].a[][]=a[l]; vl[cr].a[][]=b[l];
vl[cr].a[][]=c[l]; vl[cr].a[][]=; return;
}
int mid=l+r>>; tg[cr].init();
ls=++tot; build(l,mid,ls);
rs=++tot; build(mid+,r,rs);
vl[cr]=vl[ls]+vl[rs]; vl[cr].a[][]=r-l+;
}
void init()
{
tot=; build(,n,);
for(int i=;i<=;i++)Ml[i].init();
Ml[].a[][]=; Ml[].a[][]=; Ml[].a[][]=;
I.init();
}
void pshd(int cr)
{
if(tg[cr]==I)return;
tg[ls]=tg[ls]*tg[cr]; tg[rs]=tg[rs]*tg[cr];
vl[ls]=vl[ls]*tg[cr]; vl[rs]=vl[rs]*tg[cr];
tg[cr]=I;
}
void mdfy(int l,int r,int cr,int L,int R,int op,int v)
{
if(l>=L&&r<=R)
{
if(op<=)tp=Ml[op];
if(op==){ tp=I; tp.a[][]=v;}
if(op==){ tp=I; tp.a[][]=v;}
if(op==){ tp=I; tp.a[][]=; tp.a[][]=v;}
tg[cr]=tg[cr]*tp; vl[cr]=vl[cr]*tp; return;
}
int mid=l+r>>; pshd(cr);
if(L<=mid)mdfy(l,mid,ls,L,R,op,v);
if(mid<R)mdfy(mid+,r,rs,L,R,op,v);
vl[cr]=vl[ls]+vl[rs]; vl[cr].a[][]=r-l+;
}
Mtr qry(int l,int r,int cr,int L,int R)
{
if(l>=L&&r<=R)return vl[cr];
int mid=l+r>>; pshd(cr);
if(L>mid)return qry(mid+,r,rs,L,R);
if(R<=mid)return qry(l,mid,ls,L,R);
return qry(l,mid,ls,L,R)+qry(mid+,r,rs,L,R);
}
int main()
{
n=rdn();
for(int i=;i<=n;i++)a[i]=rdn(),b[i]=rdn(),c[i]=rdn();
init(); m=rdn(); int op,l,r,v=;
while(m--)
{
op=rdn();l=rdn();r=rdn();
if(op==)
{
Mtr ans=qry(,n,,l,r);
printf("%d %d %d\n",ans.a[][],ans.a[][],ans.a[][]);
}
if(op>=&&op<=)v=rdn();
if(op<)mdfy(,n,,l,r,op,v);
}
return ;
}
1.行向量乘4*4矩阵，写成 42 而不是 43 的。
2.矩阵乘法的时候，一定要多写很多 if(a[i][k]) 之类的判断。会快一大截！
3.查询的时候，无需返回一个矩阵，可以用全局变量去累计答案。
4.快速输出。
然后还是 95 分……但是把其他 AC 代码交上去，TLE得更严重。这到底是……
UPD(2019.5.18)：再交了一次，卡过了。
#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
#define ls Ls[cr]
#define rs Rs[cr]
using namespace std;
int rdn()
{
int ret=;bool fx=;char ch=getchar();
while(ch>''||ch<''){if(ch=='-')fx=;ch=getchar();}
while(ch>=''&&ch<='')ret=ret*+ch-'',ch=getchar();
return fx?ret:-ret;
}
int g[];
void wrt(int x)
{
int t=;
while(x)g[++t]=x%,x/=;
for(int i=t;i;i--)putchar(g[i]+'');
}
const int N=2e5+5e4+,M=5e5+,mod=;
int upt(int x){while(x>=mod)x-=mod;while(x<)x+=mod;return x;} int n,m,tot,Ls[M],Rs[M],vl[M][],s0,s1,s2,tp[];
bool lz[M];
struct Mtr{
int a[][];
Mtr(){memset(a,,sizeof a);}
void init()
{ for(int i=;i<;i++)a[i][i]=;}
Mtr operator* (const Mtr &b)const
{
Mtr c;
for(int i=;i<;i++)
for(int k=;k<;k++)
if(a[i][k])///
for(int j=;j<;j++)
if(b.a[k][j])
c.a[i][j]=(c.a[i][j]+(ll)a[i][k]*b.a[k][j])%mod;
return c;
}
Mtr operator+ (const Mtr &b)const
{
Mtr c=*this;
for(int i=;i<;i++)c.a[][i]=upt(c.a[][i]+b.a[][i]);
return c;
}
bool operator== (const Mtr &b)const
{
for(int i=;i<;i++)
for(int j=;j<;j++)if(a[i][j]!=b.a[i][j])return false;
return true;
}
}Ml[],tg[M],I,trans;
void Mul(int cr,Mtr b)
{
for(int j=;j<;j++)tp[j]=vl[cr][j],vl[cr][j]=;
tp[]=vl[cr][];
for(int k=;k<;k++)
if(tp[k])
for(int j=;j<;j++)//
if(b.a[k][j])
vl[cr][j]=(vl[cr][j]+(ll)tp[k]*b.a[k][j])%mod;
}
void Plu(int cr,int b)
{
for(int j=;j<;j++)tp[j]=upt(vl[cr][j]+vl[b][j]);
}
void build(int l,int r,int cr)
{
if(l==r)
{
vl[cr][]=rdn(); vl[cr][]=rdn();
vl[cr][]=rdn(); vl[cr][]=; return;
}
int mid=l+r>>; tg[cr].init();
ls=++tot; build(l,mid,ls);
rs=++tot; build(mid+,r,rs);
Plu(ls,rs); for(int j=;j<;j++)vl[cr][j]=tp[j];
vl[cr][]=r-l+;
}
void init()
{
tot=; build(,n,);
for(int i=;i<=;i++)Ml[i].init();
Ml[].a[][]=; Ml[].a[][]=; Ml[].a[][]=;
I.init();
}
void pshd(int cr)
{
if(!lz[cr])return; lz[cr]=;
tg[ls]=tg[ls]*tg[cr]; tg[rs]=tg[rs]*tg[cr];
Mul(ls,tg[cr]); Mul(rs,tg[cr]);//
tg[cr]=I;
lz[ls]=lz[rs]=;
}
void mdfy(int l,int r,int cr,int L,int R)
{
if(l>=L&&r<=R)
{
tg[cr]=tg[cr]*trans; Mul(cr,trans);//
lz[cr]=; return;
}
int mid=l+r>>; pshd(cr);
if(L<=mid)mdfy(l,mid,ls,L,R);
if(mid<R)mdfy(mid+,r,rs,L,R);
Plu(ls,rs); for(int j=;j<;j++)vl[cr][j]=tp[j];
}
void qry(int l,int r,int cr,int L,int R)
{
if(l>=L&&r<=R)
{
s0=upt(s0+vl[cr][]); s1=upt(s1+vl[cr][]);
s2=upt(s2+vl[cr][]); return;
}
int mid=l+r>>; pshd(cr);
if(L<=mid)qry(l,mid,ls,L,R);
if(mid<R)qry(mid+,r,rs,L,R);
}
int main()
{
n=rdn();
init(); m=rdn(); int op,l,r,v=;
while(m--)
{
op=rdn();l=rdn();r=rdn();
if(op==)
{
s0=s1=s2=;
qry(,n,,l,r);
wrt(s0);putchar(' ');
wrt(s1);putchar(' ');
wrt(s2);puts("");
continue;
}
if(op>=&&op<=)
{
v=rdn(); trans=I;
if(op==) trans.a[][]=v;
if(op==) trans.a[][]=v;
if(op==){ trans.a[][]=; trans.a[][]=v;}
}
else trans=Ml[op];
if(op<)mdfy(,n,,l,r);
}
return ;
}