清北学堂NOIP训练营内部省选模拟训练题
清北学堂2018年1月省选强化班模拟考试
#include
#include
using namespace std;
const int mod=1000000007;
#define N 100001
typedef long long LL;
LL pre1[N],pre2[N];
LL siz[N<<2];
LL sum[N<<2],sum2[N<<2],sum3[N<<2];
LL fa1[N<<2],fd[N<<2];
LL ans;
void read(int &x)
{
x=0; char c=getchar();
while(!isdigit(c)) c=getchar();
while(isdigit(c)) { x=x*10+c-'0'; c=getchar(); }
}
void read(LL &x)
{
x=0; char c=getchar();
while(!isdigit(c)) c=getchar();
while(isdigit(c)) { x=x*10+c-'0'; c=getchar(); }
}
void pre(int n)
{
for(int i=1;i<=n;++i)
{
pre1[i]=(pre1[i-1]+i*i)%mod;
pre2[i]=pre2[i-1]+i*2;
pre2[i]-=pre2[i]>=mod ? mod : 0;
}
}
void build(int k,int l,int r)
{
siz[k]=r-l+1;
if(l==r)
{
read(sum[k]);
sum2[k]=(sum[k]*sum[k])%mod;
return;
}
int mid=l+r>>1;
build(k<<1,l,mid);
build(k<<1|1,mid+1,r);
sum[k]=sum[k<<1]+sum[k<<1|1];
sum[k]-=sum[k]>=mod ? mod : 0;
sum2[k]=sum2[k<<1]+sum2[k<<1|1];
sum2[k]-=sum2[k]>=mod ? mod : 0;
sum3[k]=(sum3[k<<1]+siz[k<<1]*sum[k<<1|1]%mod+sum3[k<<1|1])%mod;
}
void insert_(int k,LL a1,LL d)
{
sum2[k]=(sum2[k]+a1*a1%mod*siz[k]%mod+d*d%mod*pre1[siz[k]-1]%mod+a1*d%mod*pre2[siz[k]-1]%mod+sum[k]*2*a1%mod+sum3[k]*d*2%mod)%mod;
sum3[k]=(sum3[k]+siz[k]*(siz[k]-1)/2%mod*a1%mod+pre1[siz[k]-1]*d%mod)%mod;
sum[k]=(sum[k]+siz[k]*a1%mod+siz[k]*(siz[k]-1)/2%mod*d%mod)%mod;
fa1[k]+=a1;
fa1[k]-=fa1[k]>=mod ? mod : 0;
fd[k]+=d;
fd[k]-=fd[k]>=mod ? mod : 0;
}
void down(int k,int s)
{
insert_(k<<1,fa1[k],fd[k]);
insert_(k<<1|1,(fa1[k]+s*fd[k])%mod,fd[k]);
fa1[k]=fd[k]=0;
}
void insert(int k,int l,int r,int opl,int opr,LL a1,LL d)
{
if(l>=opl && r<=opr)
{
insert_(k,a1,d);
return;
}
int mid=l+r>>1;
if(fa1[k] || fd[k]) down(k,mid+1-l);
if(opr<=mid) insert(k<<1,l,mid,opl,opr,a1,d);
else if(opl>mid) insert(k<<1|1,mid+1,r,opl,opr,a1,d);
else
{
insert(k<<1,l,mid,opl,mid,a1,d);
insert(k<<1|1,mid+1,r,mid+1,opr,(a1+(mid+1-opl)*d)%mod,d);
}
sum[k]=sum[k<<1]+sum[k<<1|1];
sum[k]-=sum[k]>=mod ? mod : 0;
sum2[k]=sum2[k<<1]+sum2[k<<1|1];
sum2[k]-=sum2[k]>=mod ? mod : 0;
sum3[k]=(sum3[k<<1]+siz[k<<1]*sum[k<<1|1]%mod+sum3[k<<1|1])%mod;
}
void query(int k,int l,int r,int opl,int opr,bool w)
{
if(l>=opl && r<=opr)
{
if(w) ans+=sum2[k];
else ans+=sum[k];
ans-=ans>=mod ? mod : 0;
return;
}
int mid=l+r>>1;
if(fa1[k] || fd[k]) down(k,mid+1-l);
if(opl<=mid) query(k<<1,l,mid,opl,opr,w);
if(opr>mid) query(k<<1|1,mid+1,r,opl,opr,w);
}
int main()
{
freopen("calculation.in","r",stdin);
freopen("calculation.out","w",stdout);
int n,m;
read(n); read(m);
pre(n);
build(1,1,n);
char c[3];
int l,r,b,k;
while(m--)
{
scanf("%s",c);
if(c[0]=='A')
{
read(l); read(r); read(k); read(b);
insert(1,1,n,l,r,b,k);
}
else
{
read(l); read(r);
ans=0;
query(1,1,n,l,r,c[0]=='C');
cout<<'n';< p="">
}
}
}
解析出自清北NOIP训练营学员：
线段树
设sum[i]表示区间的和，sum2[i]表示区间数的平方和
预处理pre1[i]：i^2的前缀和,pre2[i]：i*2的前缀和
现在要对区间加首项为a1，公差为d的等差数列
假设区间有4个数，A、B、C、D，区间大小siz=4
原来的sum[i]=A+B+C+D
现在的sum[i]=A+a1+B+a1+d+C+a1+2d+D+a1+3d
即新的sum[i]=原来的sum[i]+siz*a1+（siz-1）*siz*d
原来的sum2[i]=A^2+B^2+C^2+D^2
现在的sum2[i]=（A+a1）^2 + (B+a1+d)^2 + (C+a1+2d)^2 + (D+a1+3d)^2
=A^2+a1^2+2*A*a1 + B^2+a1^2+d^2+2*B*a1+2*B*d+2*a1*d + C^2+a1^2+4*d^2+2*C*a1+4*C*d+4*a1*d + D^2+a1^2+9*d^2+2*D*a1+6*D*d+6*a1*d
=(A^2+B^2+C^2+D^2)+(a1^2+a1^2+a1^2+a1^2)+(d^2+4*d^2+9*d^2)+(2*A*a1+2*B*a1+2*C*a1+2*D*a1)+(2*a1*d+4*a1*d+6*a1*d)+(2*B*d+4*C*d+6*D*d)
=原来的sum2[i]+siz*a1^2+pre[siz-1]*d^2+2*原来的sum[i]*a1+pre[siz-1]*a1*d+pre[siz-1]*a1*d+ (2*B*d+4*C*d+6*D*d)
最后的那个怎么维护？
令sum3[i]表示0*A+1*B+2*C+3*D……
最后那个就是sum[3]*2*d
合并时，sum，sum2直接合并
sum3[k]=sum3[L]+sum3[R]+siz[L]*sum[R]
L：0*A+1*B+2*C
R：0*D+1*E+2*F
合并后：0*A+1*B+2*C+3*D+4*E+5*F
合并后R的部分与子区间的R每个值差了siz[L]倍
声明：本文章由网友投稿作为教育分享用途，如有侵权原作者可通过邮件及时和我们联系删除：freemanzk@qq.com
