清北学堂NOIP训练营内部省选模拟训练题

转自公众号:信息学竞赛 2019-12-26 15:11


清北学堂2018年1月省选强化班模拟考试

https://cdn.china-scratch.com/timg/191228/151132F01-0.jpg

#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]倍

本文转自公众号:信息学竞赛

后记,小编朋友公司研发了一个游戏化的少儿编程在线课程(5-12岁),游戏化教学结合scratch(一款在线少儿编程工具,类似乐高的积木拼搭),我家娃娃学了几次课,非常喜欢(超预期),16次课才200多块钱,对锻炼孩子的思维能力和动手动力很有帮助。

感兴趣的朋友可以扫描二维码,关注一下,或微信搜索“大耳猴少儿编程”

https://www.china-scratch.com/Uploads/Editor/2018-04-22/5adca08bdc212.jpg

声明:本文章由爬虫自动处理和转载作为教育分享用途,原作者可通过邮件及时和我们联系处理:freemanzk@qq.com