先致敬 houzhe 学长经典：
我看到我的队友写了个又臭又长的线段树，维护了一堆 tag，于是一脚把他踹下去，写了个线段树维护矩阵，然后就过了。
回到这题，题意即为求一段连续的版本 \([x,y]\) 中,所有版本的区间 \([l,r]\) 的值的平方和。
首先显然可以变成 \([1,y]\) 版本的答案减去 \([1,x]\) 版本的答案。然后变成一个历史版本和问题。解决历史版本和问题自然会想到维护矩阵。当然你打 tag 也是可以的，但是这样的话建议还是从矩阵的角度去推更新，否则很容易出问题。
具体地，SGT 上每个位置维护一个 \(4\times 4\) 的矩阵，记录区间和，区间平方和，区间长度和区间历史版本和四个量，把 \(\sum(a_i+k)^2\) 套路化地拆成 \(\sum a_i^2+\sum a_i\times k+len\times k^2\)，这也是一个矩阵很好维护的形式。每做完一次操作之后更新历史和即可。
细节不是很多，需要注意的有：
-
tag 的矩阵初始值是单位矩阵而不是全 \(0\) 矩阵。
-
\(a_i\) 和更新的 \(x\) 都可能是负数。
结束了。跑的还挺快……吗？至少过了而且不是最劣解。/kk
code：
点击查看代码
int n,m,q,a[N],ans[N];
struct node{int l,r,x;}b[N];
struct Node{int l,r,s,id;};
vector<Node> g[N];
il int Mod(int x,int y){return x+y>=mod?x+y-mod:x+y;}
struct SGT{
struct mat{
int a[4][4];
mat(){mems(a,0);}
il void reset(){mems(a,0);rep(i,0,3)a[i][i]=1;}
il mat operator*(const mat &rhs)const{
mat r;
rep(k,0,3)rep(i,0,3)rep(j,0,3)r.a[i][j]=Mod(r.a[i][j],1ll*a[i][k]*rhs.a[k][j]%mod);
return r;
}
il mat operator+(const mat &rhs)const{
mat r;
rep(i,0,3)rep(j,0,3)r.a[i][j]=Mod(a[i][j],rhs.a[i][j]);
return r;
}
};
struct Tnode{mat x,tag;}tr[N<<2];
il void pushup(int o){tr[o].x=tr[o<<1].x+tr[o<<1|1].x;}
il void reset(int o,mat &k){tr[o].x=tr[o].x*k,tr[o].tag=tr[o].tag*k;}
il void pushdown(int o){reset(o<<1,tr[o].tag),reset(o<<1|1,tr[o].tag),tr[o].tag.reset();}
void build(int l,int r,int o){
tr[o].tag.reset();
if(l==r)return tr[o].x.a[0][0]=Mod(a[l],mod),tr[o].x.a[0][1]=1ll*a[l]*a[l]%mod,tr[o].x.a[0][2]=1,void();
int mid=(l+r)>>1;
build(l,mid,o<<1),build(mid+1,r,o<<1|1);
pushup(o);
}
void update(int l,int r,int o,int x,int y,mat k){
if(l>=x&&r<=y)return reset(o,k);
pushdown(o);
int mid=(l+r)>>1;
if(x<=mid)update(l,mid,o<<1,x,y,k);
if(y>mid)update(mid+1,r,o<<1|1,x,y,k);
pushup(o);
}
int query(int l,int r,int o,int x,int y){
if(r<x||l>y)return 0;
if(l>=x&&r<=y)return tr[o].x.a[0][3];
pushdown(o);
int mid=(l+r)>>1;
return Mod(query(l,mid,o<<1,x,y),query(mid+1,r,o<<1|1,x,y));
}
}T;
void Yorushika(){
scanf("%d%d%d",&n,&m,&q),m++;
rep(i,1,n)scanf("%d",&a[i]);
rep(i,2,m)scanf("%d%d%d",&b[i].l,&b[i].r,&b[i].x);
rep(i,1,q){
int l,r,x,y;scanf("%d%d%d%d",&l,&r,&x,&y);
g[x].eb((Node){l,r,-1,i}),g[y+1].eb((Node){l,r,1,i});
}
T.build(1,n,1),b[1]={1,1,0};
SGT::mat x;x.reset();
rep(i,1,m){
SGT::mat tmp;int x=b[i].x;
tmp.a[0][0]=1,tmp.a[0][1]=Mod(2ll*x%mod,mod);
tmp.a[1][1]=1;
tmp.a[2][0]=Mod(x,mod),tmp.a[2][1]=1ll*x*x%mod,tmp.a[2][2]=1;
tmp.a[3][3]=1;
T.update(1,n,1,b[i].l,b[i].r,tmp);
tmp.reset(),tmp.a[1][3]=1;
T.reset(1,tmp);
for(Node j:g[i])ans[j.id]=Mod(ans[j.id],Mod(mod,T.query(1,n,1,j.l,j.r)*j.s));
}
rep(i,1,q)printf("%d\n",ans[i]);
}
signed main(){
int t=1;
// scanf("%d",&t);
while(t--)
Yorushika();
}