[Luogu 3707] SDOI2017 相关分析

<题目链接>

---

前言

概述

准备与计算答案

区间加操作

区间修改操作

前置技能

\(1^2 + 2^2 + \dots + n^2 = \frac {n(n+1)(2n+1)} 6\)

转化

维护操作

注意事项

结束语

#include <cstdio>

#include <cstring>

const int MAXN=100010;

double x[MAXN],y[MAXN];

int n,m;

class SegmentTree

{

    public:

        void Build(int i,int l,int r)

        {

            s[i]=node(l,r);

            if(l==r)

            {

                s[i].v[0]=x[l]*x[l],s[i].v[1]=x[l]*y[r],s[i].v[2]=x[l],s[i].v[3]=y[r];

                return;

            }

            int j=i<<1,mid=l+r>>1;

            Build(j,l,mid),Build(j|1,mid+1,r),PushUp(i);

        }

        void Add(int i,int l,int r,double S,double T)

        {

            if(l==s[i].l && r==s[i].r)

            {

                AddModify(i,S,T);

                return;

            }

            if(s[i].l^s[i].r)

                PushDown(i);

            int j=i<<1,mid=s[i].l+s[i].r>>1;

            if(r<=mid)

                Add(j,l,r,S,T);

            else if(l>mid)

                Add(j|1,l,r,S,T);

            else

                Add(j,l,mid,S,T),Add(j|1,mid+1,r,S,T);

            PushUp(i);

        }

        void Change(int i,int l,int r,double S,double T)

        {

            if(l==s[i].l && r==s[i].r)

            {

                ChangeModify(i),AddModify(i,S,T);

                return;

            }

            if(s[i].l^s[i].r)

                PushDown(i);

            int j=i<<1,mid=s[i].l+s[i].r>>1;

            if(r<=mid)

                Change(j,l,r,S,T);

            else if(l>mid)

                Change(j|1,l,r,S,T);

            else

                Change(j,l,mid,S,T),Change(j|1,mid+1,r,S,T);

            PushUp(i);

        }

        double Ans(double l,double r)

        {

            double size=r-l+1;

            memset(ans,0,sizeof ans);

            Sum(1,l,r);

            return (ans[1]-ans[2]*ans[3]/size)/(ans[0]-ans[2]*ans[2]/size);

        }

    private:

        double ans[4];

        struct node

        {

            bool c;

            double S,T,v[4];

            int l,r;

            node(int _l=0,int _r=0)

            {

                l=_l,r=_r,c=S=T=0;

            }

        }s[MAXN<<2];

        double Calc(double i)

        {

            return i*(i+1)*(2*i+1)/6;

        }

        void AddModify(int i,double S,double T)

        {

            double size=double(s[i].r-s[i].l+1);

            s[i].v[0]+=S*S*size+2*S*s[i].v[2];

            s[i].v[1]+=S*T*size+S*s[i].v[3]+T*s[i].v[2];

            s[i].v[2]+=S*size;

            s[i].v[3]+=T*size;

            s[i].S+=S,s[i].T+=T;

        }

        void ChangeModify(int i)

        {

            double l=double(s[i].l),r=double(s[i].r);

            s[i].v[0]=s[i].v[1]=Calc(r)-Calc(l-1),s[i].v[2]=s[i].v[3]=(r-l+1)*(l+r)/2,s[i].c=1,s[i].S=s[i].T=0;

        }

        void PushUp(int i)

        {

            int l=i<<1,r=l|1;

            for(int k=0;k<4;++k)

                s[i].v[k]=s[l].v[k]+s[r].v[k];

        }

        void PushDown(int i)

        {

            int l=i<<1,r=l|1;

            if(s[i].c)

                ChangeModify(l),ChangeModify(r);

            AddModify(l,s[i].S,s[i].T),AddModify(r,s[i].S,s[i].T);

            s[i].c=s[i].S=s[i].T=0;

        }

        void Sum(int i,int l,int r)

        {

            if(l==s[i].l && r==s[i].r)

            {

                for(int k=0;k<4;++k)

                    ans[k]+=s[i].v[k];

                return;

            }

            if(s[i].l^s[i].r)

                PushDown(i);

            int j=i<<1,mid=s[i].l+s[i].r>>1;

            if(r<=mid)

                Sum(j,l,r);

            else if(l>mid)

                Sum(j|1,l,r);

            else

                Sum(j,l,mid),Sum(j|1,mid+1,r);

        }

}SgT;

int main(int argc,char *argv[])

{

    scanf("%d %d",&n,&m);

    for(int i=1;i<=n;++i)

        scanf("%lf",&x[i]);

    for(int i=1;i<=n;++i)

        scanf("%lf",&y[i]);

    SgT.Build(1,1,n);

    for(int i=1,opt,l,r;i<=m;++i)

    {

        double S,T;

        scanf("%d %d %d",&opt,&l,&r);

        switch(opt)

        {

            case 1:

                printf("%.10lf\n",SgT.Ans(l,r));

                break;

            case 2:

                scanf("%lf %lf",&S,&T);

                SgT.Add(1,l,r,S,T);

                break;

            case 3:

                scanf("%lf %lf",&S,&T);

                SgT.Change(1,l,r,S,T);

                break;

        }

    }

    return 0;

}