原文链接http://www.cnblogs.com/zhouzhendong/p/9031130.html

题目传送门 - LOJ#2512

题目传送门 - 洛谷P4458

题目传送门 - BZOJ5291

推荐LOJ和洛谷,题面质量好,而且不卡常数。

BZOJ题面烂,而且要卡那么一点点常数。

题意

  有一条长度为$n$的链$\forall 1≤i<n$,点$i$与点$i+1$之间有一条边的无向图),每个点有一个整数权值,第$i$个点的权值是$a_i$​​。现在有$m$个操作,每个操作如下:

  操作 1(修改):给定链上两个节点$u$、$v$和一个整数$d$,表示将链上$u$到$v$唯一的简单路径上每个点权值都加上$d$。

  操作 2(询问):给定两个正整数$L$、$R$,表示求链上所有节点个数大于等于$L$且小于等于$R$的简单路径节点权值和之和。由于答案很大,只用输出对质数$1000000007$取模的结果即可。

  一条节点个数为$k$的简单路径节点权值和为这条上所有$k$个节点(包括端点)的权值之和,而本题中要求是对所有满足要求的简单路径,求这一权值和的和。

  由于是无向图,路径也是无向的,即点$1$到点$2$的路径与点$2$到点$1$的路径是同一条,不要重复计算。

题解

  记$S_x[i]=\sum_{j=1}^{i} x[j]$,则我们现在来推一下式子。

  对于询问,我们要求的是:

$$\begin{align*}\sum_{i=L}^{R}\sum_{j=i}^{n}S_a[j]-S_a[j-i]&=\sum_{i=L}^{R}(\sum_{j=i}^{n}S_a[j]-\sum_{j=0}^{n-i}S_a[j])\\&=\sum_{i=L}^{R}(S_{S_a}[n]-S_{S_a}[i-1]-S_{S_a}[n-i])\\&=(R-L+1)S_{S_a}[n]-\sum_{i=L-1}^{R-1}S_{S_a}[i]-\sum_{n-R}^{n-L}S_{S_a}[i]\end{align*}$$

  只需要维护$S_{S_a}$的前缀和就可以了。

  考虑分类讨论区间加对$S_{S_a}$的贡献。

  在$L$~$R$区间加$v$的贡献为:

  记$len=R-L+1$,

  对于$L\leq i\leq R$,$S_{S_a}[i]=S_{S_a}[i]+\cfrac{(i-L+1)(i-L+2)}{2}v$。

  对于$i>R$,$S_{S_a}[i]=S_{S_a}[i]+\cfrac{len(len+1)}{2}v+len(i-R)v$。

  注意一下,对于修改,$L$和$R$可能是$L>R$的,我这里默认了$L\leq R$。

  于是这个区间加对于$S_{S_a}$的贡献可以转化成一个关于$i$的二次函数。

  可以用线段树来维护。

  在BZOJ上面,略微卡一点常数。建议在标记下传的时候,如果三个标记都为$0$就直接退出。

题解参考了:https://blog.csdn.net/cdsszjj/article/details/80286084

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=200005;
const LL mod=1e9+7;
int n,m,a[N];
LL cv1[N],cv2[N];
struct Seg{
LL v,v0,v1,v2;
LL s0,s1,s2;
}t[N<<2];
void build(int rt,int L,int R){
t[rt].v0=t[rt].v1=t[rt].v2=0;
t[rt].s0=R-L+1;
if (L>0){
t[rt].s1=(cv1[R]-cv1[L-1]+mod)%mod;
t[rt].s2=(cv2[R]-cv2[L-1]+mod)%mod;
}
else
t[rt].s1=cv1[R],t[rt].s2=cv2[R];
if (L==R){
t[rt].v=a[L];
return;
}
int mid=(L+R)>>1,ls=rt<<1,rs=ls|1;
build(ls,L,mid);
build(rs,mid+1,R);
t[rt].v=(t[ls].v+t[rs].v)%mod;
}
void addrt(int rt,LL d0,LL d1,LL d2){
t[rt].v=(t[rt].v+d0*t[rt].s0+d1*t[rt].s1+d2*t[rt].s2)%mod;
t[rt].v0=t[rt].v0+d0;
t[rt].v1=t[rt].v1+d1;
t[rt].v2=t[rt].v2+d2;
if (t[rt].v0>=mod)t[rt].v0-=mod;
if (t[rt].v1>=mod)t[rt].v1-=mod;
if (t[rt].v2>=mod)t[rt].v2-=mod;
}
void pushdown(int rt){
if (!t[rt].v0&&!t[rt].v1&&!t[rt].v2)
return;
int ls=rt<<1,rs=ls|1;
addrt(ls,t[rt].v0,t[rt].v1,t[rt].v2);
addrt(rs,t[rt].v0,t[rt].v1,t[rt].v2);
t[rt].v0=t[rt].v1=t[rt].v2=0;
}
void update(int rt,int L,int R,int xL,int xR,LL d0,LL d1,LL d2){
if (xL>xR)
return;
if (xL<=L&&R<=xR){
addrt(rt,d0,d1,d2);
return;
}
int mid=(L+R)>>1,ls=rt<<1,rs=ls|1;
pushdown(rt);
if (xR<=mid)
update(ls,L,mid,xL,xR,d0,d1,d2);
else if (xL>mid)
update(rs,mid+1,R,xL,xR,d0,d1,d2);
else {
update(ls,L,mid,xL,mid,d0,d1,d2);
update(rs,mid+1,R,mid+1,xR,d0,d1,d2);
}
t[rt].v=(t[ls].v+t[rs].v)%mod;
}
LL query(int rt,int L,int R,int xL,int xR){
if (xL>xR)
return 0;
if (xL<=L&&R<=xR)
return t[rt].v;
int mid=(L+R)>>1,ls=rt<<1,rs=ls|1;
pushdown(rt);
if (xR<=mid)
return query(ls,L,mid,xL,xR);
else if (xL>mid)
return query(rs,mid+1,R,xL,xR);
else
return (query(ls,L,mid,xL,xR)+query(rs,mid+1,R,xL,xR))%mod;
}
int main(){
scanf("%d%d",&n,&m);
for (int i=1;i<=n;i++){
cv1[i]=(cv1[i-1]+i)%mod;
cv2[i]=(cv2[i-1]+1LL*i*i)%mod;
}
for (int i=1;i<=n;i++)
scanf("%d",&a[i]),a[i]=(a[i]+a[i-1])%mod;
for (int i=1;i<=n;i++)
a[i]=(a[i]+a[i-1])%mod;
build(1,1,n);
for (int i=1;i<=m;i++){
int opt,L,R;
LL v;
scanf("%d%d%d",&opt,&L,&R);
if (L>R)
swap(L,R);
if (opt==2){
L=max(L,1);
LL s1=query(1,1,n,n,n)*(R-L+1)%mod;
LL s2=query(1,1,n,max(L-1,1),R-1);
LL s3=query(1,1,n,max(n-R,1),n-L);
printf("%lld\n",(s1-s2-s3+mod+mod+mod)%mod);
}
else {
scanf("%lld",&v);
LL len=R-L+1,iv2=500000004,vv=v*iv2%mod;
update(1,1,n,L,R,vv*(L-1)%mod*(L-2)%mod,vv*(3-2*L+mod)%mod,vv);
update(1,1,n,R+1,n,((len*(len+1)/2%mod*v-len*v%mod*R)%mod+mod)%mod,v*len%mod,0);
}
}
return 0;
}

  

05-11 11:10