P4458
居然有个高手
·
·
个人记录
考虑直接算算不了一点，打算拆个贡献。拆贡献到每个点上，则其每个点权的贡献是个神秘二次多项式，不好做。考虑拆到前缀和上。
$ans = \sum (sum_r - sum_l)[L<=r-l<=R]$，$sum_r$ 与 $sum_l$ 贡献显然分离，分开计算。考虑 $sum_l$ 的计算（$sum_r$ 对偶），发现若 $l\in [n-L+1,n]$ 则无贡献；$l\in [n-R+1,n-L]$ 则 $sum_l$ 贡献为 $-(n+1-L-l)$；$l\in [0,n-R]$ 则贡献为 $-(R-L+1)$。则我们只需要维护 $sum_i$ 的和与 $sum_i\times i$ 的和即可，其余都是常数。
考虑区间加 $d$，相当于给 $sum_i$ 区间加等差数列，对 $sum_i$ 的影响为 $d\times (i-L+1)$，对 $sum_i\times i$ 的影响为 $d\times (i-l+1)\times i$，我们只需要在分离常数项与变量，转变为一次区间加常数，一次区间加等差数列，过程中求个 $\sum_{j=1}^{i}j^2$ 即可。在线段树上维护打两个 tag 分别表示区间加 $c$ 与区间加公差为 $c$ 的等差数列。
时间复杂度：$O(n\log n)$。
```cpp
#include <bits/stdc++.h>
using namespace std;
const int N=2e5+5,mod=1e9+7;
inline int read(){
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
return x*f;
}
int n,q,a[N];
inline long long calc1(int x){
return x*(x+1ll)/2%mod;
}
inline long long calc2(int x){
return x*(x+1ll)*(2ll*x+1)/6%mod;
}
struct tree{
int p,l,r;
long long sum1,sum2,tag1,tag2;
}t[N<<2];
#define mid (t[p].l+t[p].r>>1)
inline void up(int p){
t[p].sum1=(t[p<<1].sum1+t[p<<1|1].sum1)%mod;
t[p].sum2=(t[p<<1].sum2+t[p<<1|1].sum2)%mod;
}
inline void build(int p,int l,int r){
t[p].l=l,t[p].r=r;
if(l==r){
t[p].sum1=a[l];
t[p].sum2=a[l]*1ll*l%mod;
return;
}
build(p<<1,l,mid),build(p<<1|1,mid+1,r);
up(p);
}
inline void cg1(int p,long long v){
t[p].tag1=(t[p].tag1+v)%mod;
t[p].sum1=(t[p].sum1 + v*(t[p].r-t[p].l+1ll))%mod;
t[p].sum2=(t[p].sum2 + v*(calc1(t[p].r) - calc1(t[p].l-1)))%mod;
}
inline void cg2(int p,long long v){
t[p].tag2=(t[p].tag2+v)%mod;
t[p].sum1=(t[p].sum1 + v*1ll*(calc1(t[p].r) - calc1(t[p].l-1)))%mod;
t[p].sum2=(t[p].sum2 + v*1ll*(calc2(t[p].r) - calc2(t[p].l-1)))%mod;
}
inline void spread(int p){
if(t[p].tag1){
cg1(p<<1,t[p].tag1),cg1(p<<1|1,t[p].tag1);
t[p].tag1=0;
}
if(t[p].tag2){
cg2(p<<1,t[p].tag2),cg2(p<<1|1,t[p].tag2);
t[p].tag2=0;
}
}
inline void change(int p,int l,int r,int op,int v){
if(l<=t[p].l&&t[p].r<=r){
if(op==0)cg1(p,v);
else cg2(p,v);
return;
}
spread(p);
if(l<=mid)change(p<<1,l,r,op,v);
if(r>mid)change(p<<1|1,l,r,op,v);
up(p);
}
inline long long query(int p,int l,int r,int op){
if(l<=t[p].l&&t[p].r<=r){
if(op==0)return t[p].sum1;
return t[p].sum2;
}
spread(p);
long long ans = 0;
if(l<=mid)ans=query(p<<1,l,r,op);
if(r>mid)ans=(ans+query(p<<1|1,l,r,op))%mod;
return ans;
}
int main(){
n=read();q=read();
for(int i = 1;i<=n;i++)a[i]=(read()+a[i-1])%mod;
build(1,0,n);
int op,l,r,d;
while(q--){
op=read(),l=read(),r=read();
if(l>r)swap(l,r);
if(op==1){
d=read();
change(1,l,r,0,d*1ll*(mod+1-l)%mod);
change(1,l,r,1,d);
if(r<n)change(1,r+1,n,0,d*(r-l+1ll)%mod);
}
else{
long long ans = 0;
if(l!=r){
ans = query(1,n-r+1,n-l,1);
ans = (ans - query(1,n-r+1,n-l,0)*(n+1ll-l))%mod;
}
ans = (ans - query(1,0,n-r,0)*(r-l+1ll))%mod;
if(l!=r){
ans = (ans + query(1,l,r-1,1))%mod;
ans = (ans - query(1,l,r-1,0)*(l-1ll))%mod;
}
ans=(ans + query(1,r,n,0)*(r-l+1ll))%mod;
printf("%lld\n",(ans+mod)%mod);
}
}
return 0;
}
```