用线段树对每种长度的区间维护权值和。
考虑区间[l,r]+1对长度为k的区间的贡献，显然其为Σk-max(0,k-i)-max(0,k-(n-i+1)) (i=l~r)。
大力展开讨论。首先变成Σk-Σmax(0,k-i)-Σmax(0,k-(n-i+1)) (i=l~r)。
第一部分是一个常数，线段树上是加了一个等差数列。打上标记即可。
后面两部分本质相同，现考虑Σmax(0,k-i) (i=l~r)。去掉max，即Σk-i (i=l~min(r,k))。根据r和k的大小关系讨论。若r<=k，线段树上加了一个一次函数；若r>k，线段树上加了一个二次函数。三种标记即可。
常数巨大，下传标记时判一下是否有标记需要传可以快至少一倍。读入序列直接当做修改就能跑过。
#include<iostream> #include<cstdio> #include<cmath> #include<cstdlib> #include<cstring> #include<algorithm> using namespace std; #define ll long long #define N 200010 #define P 1000000007 #define inv 500000004 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,a[N],s[3][N]; struct data{int l,r,sum,lazy[3]; }tree[N<<2]; inline void inc(int &x,int y){x+=y;if (x>=P) x-=P;} inline void up(int k){tree[k].sum=tree[k<<1].sum+tree[k<<1|1].sum;if (tree[k].sum>=P) tree[k].sum-=P;} inline void update(int k,int x,int op) { inc(tree[k].sum,1ll*x*(s[op][tree[k].r]-s[op][tree[k].l-1]+P)%P); inc(tree[k].lazy[op],x); } inline void down(int k,int i) { update(k<<1,tree[k].lazy[i],i), update(k<<1|1,tree[k].lazy[i],i), tree[k].lazy[i]=0; } void build(int k,int l,int r) { tree[k].l=l,tree[k].r=r; if (l==r) return; int mid=l+r>>1; build(k<<1,l,mid); build(k<<1|1,mid+1,r); } void add(int k,int l,int r,int x,int op) { if (l>r) return; if (tree[k].l==l&&tree[k].r==r) {update(k,x,op);return;} if (tree[k].lazy[0]) down(k,0); if (tree[k].lazy[1]) down(k,1); if (tree[k].lazy[2]) down(k,2); int mid=tree[k].l+tree[k].r>>1; if (r<=mid) add(k<<1,l,r,x,op); else if (l>mid) add(k<<1|1,l,r,x,op); else add(k<<1,l,mid,x,op),add(k<<1|1,mid+1,r,x,op); up(k); } int query(int k,int l,int r) { if (tree[k].l==l&&tree[k].r==r) return tree[k].sum; if (tree[k].lazy[0]) down(k,0); if (tree[k].lazy[1]) down(k,1); if (tree[k].lazy[2]) down(k,2); int mid=tree[k].l+tree[k].r>>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))%P; } void modify(int l,int r,int x) { add(1,r,n,1ll*(r-l+1)*x%P,1),add(1,r,n,P-1ll*(s[1][r]-s[1][l-1]+P)*x%P,0); add(1,l,r-1,1ll*x*inv%P,2),add(1,l,r-1,1ll*x*(P+1-l-inv)%P,1),add(1,l,r-1,1ll*l*(l-1)%P*inv%P*x%P,0); } void change(int l,int r,int x) { add(1,1,n,1ll*(r-l+1)*x%P,1); modify(l,r,P-x),modify(n-r+1,n-l+1,P-x); } int main() { #ifndef ONLINE_JUDGE freopen("bzoj5291.in","r",stdin); freopen("bzoj5291.out","w",stdout); const char LL[]="%I64d\n"; #else const char LL[]="%lld\n"; #endif n=read(),m=read(); build(1,1,n); for (int i=1;i<=n;i++) s[0][i]=s[0][i-1]+1,s[1][i]=(s[1][i-1]+i)%P,s[2][i]=(s[2][i-1]+1ll*i*i)%P; for (int i=1;i<=n;i++) change(i,i,read()); while (m--) { int op=read(); if (op==1) { int l=read(),r=read(),x=read(); if (l>r) swap(l,r); change(l,r,x); } else { int l=read(),r=read(); printf("%d\n",query(1,l,r)); } } return 0; }
原文：https://www.cnblogs.com/Gloid/p/10111186.html