自动搬运

查看原文

来自洛谷，原作者为

	Raymondzll **

搬运于2025-08-24 22:00:23，当前版本为作者最后更新于2022-04-11 10:42:22，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

P4458 链上二次求和

前言

尽量做到一气呵成，会 sigma 的小学生都能看懂，因为真的就是线段树和推式子。

解题思路

记原链表为 $a$，一次前缀和 $S_a$ 记为 $S$，二次前缀和 $S_{S_a}$ 记为 $SS$。

$\begin{aligned} &\sum\limits_{k=l}^{r}\sum\limits_{i=k}^{n}\sum\limits_{j=i-k+1}^{i}a_j \\&=\sum\limits_{k=l}^{r}\sum\limits_{i=k}^{n}S_i-S_{i-k} \\&=\sum\limits_{k=l}^{r}(\sum\limits_{i=k}^{n}S_i-\sum\limits_{j=0}^{n-k}S_j) \\&=\sum\limits_{k=l}^{r}(SS_n-SS_{k-1}-SS_{n-k}) \\&=(r-l+1)SS_n-\sum\limits_{k=l-1}^{r-1}SS_k-\sum\limits_{k=n-r}^{n-l}SS_k \end{aligned}$

我们要维护 $\sum\limits_{k=l}^{r}SS_k$，支持区间修改。

当对 $l\sim r$ 加上 $\Delta$ 时，

对于 $l\le i\le r$ 的 $i$，$SS_i$ 加上 $\frac{(i-l+1)(i-l+2)}{2}\times\Delta$。

对于 $r< i\le n$ 的 $i$，$SS_i$ 加上 $\frac{(r-l+1)(r-l+2)}{2}\times\Delta+(i-r)(r-l+1)\times\Delta$。

最后一点，lazy 数组可以用三个数 la,lb,lc 三个数表示，代表 val[id] 需要加上 $\sum\limits_ {i=l}^r{la\times i^2+lb\times i+lc}$。

相信没有什么疑问了吧。

细节

1. 可能出现 $l>r$。

2. 除以 $2$ 和 $6$ 就算出 $2$ 和 $6$ 在 $\pmod{1000000007}$ 下的逆元就行。

3. 注意负数和各种奇怪的溢出。

4. 不要写着写着忘了式子，坚定信念，也就一百多行。

代码部分

#include <bits/stdc++.h>
using namespace std;
void file(string str){
	freopen((str+".in").c_str(),"r",stdin);
	freopen((str+".out").c_str(),"w",stdout);
}
const int MAXN=200010;
const int mod=1e9+7,inv2=5e8+4,inv6=inv2/3;
int n,m,init[MAXN],s[MAXN],ss[MAXN];
int val[MAXN<<2],laa[MAXN<<2],lab[MAXN<<2],lac[MAXN<<2];
inline int ad(int a,int b){return (a+b)%mod;}
inline int add(int a,int b,int c=0,int d=0){return ad(ad(a,b),ad(c,d));}
inline int mu(int a,int b){return 1ll*a*b%mod;}
inline int mul(int a,int b,int c=1,int d=1){return mu(mu(a,b),mu(c,d));}
int p1sum(int a){return mul(a,a+1,inv2);}
int p2sum(int a){return mul(a,a+1,2*a+1,inv6);}
int p1sum(int a,int b){return p1sum(b)-p1sum(a-1);}
int p2sum(int a,int b){return p2sum(b)-p2sum(a-1);}
void ___(int &a){a%=mod;if(a<0)a+=mod;}
void pushup(int id){val[id]=add(val[id<<1],val[id<<1|1]);}
void tag(int id,int l,int r,int la,int lb,int lc){
	val[id]=add(val[id],mul(la,p2sum(l,r)),mul(lb,p1sum(l,r)),mul(lc,r-l+1));
	___(val[id]);laa[id]=add(laa[id],la);lab[id]=add(lab[id],lb);lac[id]=add(lac[id],lc);
}
void pushdown(int id,int l,int r){
	if(laa[id]||lab[id]||lac[id]){
		int mid=(l+r)>>1;
		tag(id<<1,l,mid,laa[id],lab[id],lac[id]);
		tag(id<<1|1,mid+1,r,laa[id],lab[id],lac[id]);
		laa[id]=lab[id]=lac[id]=0;
	}
}
void update(int id,int l,int r,int ql,int qr,int la,int lb,int lc){
	if(r<ql||l>qr)return;
	if(l>=ql&&r<=qr){tag(id,l,r,la,lb,lc);return;}
	int mid=(l+r)>>1;pushdown(id,l,r);
	update(id<<1,l,mid,ql,qr,la,lb,lc);
	update(id<<1|1,mid+1,r,ql,qr,la,lb,lc);
	pushup(id);
}
int query(int id,int l,int r,int ql,int qr){
	if(r<ql||l>qr)return 0;
	if(l>=ql&&r<=qr)return val[id];
	int mid=(l+r)>>1;pushdown(id,l,r);
	return add(query(id<<1,l,mid,ql,qr),query(id<<1|1,mid+1,r,ql,qr));
}
void build(int id,int l,int r){
	if(l==r){val[id]=ss[l];return;}
	int mid=(l+r)>>1;
	build(id<<1,l,mid);build(id<<1|1,mid+1,r);pushup(id);
}
void UPDATE(int l,int r,int d){
	int inv2_d=mul(inv2,d);
	update(1,1,n,l,r,inv2_d,mul((mod+3-2*l),inv2_d),mul(l-1,l-2,inv2_d));
	int tmp1=mul(p1sum(r-l+1),d),tmp2=mul(r-l+1,d);
	if(r<n)update(1,1,n,r+1,n,0,tmp2,tmp1-mul(tmp2,r));
}
int QUERY(int l,int r){
	int res=mul(r-l+1,query(1,1,n,n,n));
	res-=query(1,1,n,l-1,r-1);res-=query(1,1,n,n-r,n-l);
	___(res);return res;
}
void initt(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){
		scanf("%d",&init[i]);
		s[i]=add(s[i-1],init[i]);ss[i]=add(ss[i-1],s[i]);
	}
	build(1,1,n);
}
int main(){
	initt();
	for(int i=1;i<=m;i++){
		int op,a,b,c;
		scanf("%d%d%d",&op,&a,&b);
		if(op==1){scanf("%d",&c);if(a>b)swap(a,b);UPDATE(a,b,c);}
		else printf("%d\n",QUERY(a,b));
	}
	return 0;
}