AC日记——[SDOI2017]相关分析 洛谷 P3707

[SDOI2017]相关分析

思路：

　　裸线段树；

　　（玄学ac）；

代码：

#include <bits/stdc++.h>

using namespace std;

#define maxn 100005

struct TreeNodeType {

    int l,r,mid;

    double flagx2,flagy2,flagx3,flagy3,size;

    double sumx,sumy,suml,sumxy,sumx2,sumy2,suml2;

    bool if_3;

    inline void updata2(double posx,double posy)

    {

        sumx2+=size*posx*posx+*posx*sumx;

        sumy2+=size*posy*posy+*posy*sumy;

        sumxy+=size*posx*posy+sumx*posy+sumy*posx;

        sumx+=size*posx,sumy+=size*posy;

        flagx2+=posx,flagy2+=posy;

    }

    inline void updata3(double posx,double posy)

    {

        sumxy=size*posx*posy+suml*(posx+posy)+suml2;

        sumx2=size*posx*posx+posx**suml+suml2;

        sumy2=size*posy*posy+posy**suml+suml2;

        sumx=size*posx+suml,sumy=size*posy+suml;

        if_3=true,flagx3=posx,flagy3=posy;

        flagx2=,flagy2=;

    }

};

struct TreeNodeType tree[maxn<<];

int n,m;

double Sumx,Sumy,Sumx2,Sumy2,Sumxy,ai[maxn],bi[maxn];

inline void updata(int now)

{

    tree[now].sumx=tree[now<<].sumx+tree[now<<|].sumx;

    tree[now].sumy=tree[now<<].sumy+tree[now<<|].sumy;

    tree[now].suml=tree[now<<].suml+tree[now<<|].suml;

    tree[now].sumxy=tree[now<<].sumxy+tree[now<<|].sumxy;

    tree[now].sumx2=tree[now<<].sumx2+tree[now<<|].sumx2;

    tree[now].sumy2=tree[now<<].sumy2+tree[now<<|].sumy2;

    tree[now].suml2=tree[now<<].suml2+tree[now<<|].suml2;

}

void build(int now,int l,int r)

{

    tree[now].l=l,tree[now].r=r,tree[now].size=r-l+;

    if(l==r)

    {

        tree[now].sumx=ai[l],tree[now].sumy=bi[l],tree[now].suml=l;

        tree[now].sumxy=ai[l]*bi[l],tree[now].suml2=(double)l*l;

        tree[now].sumx2=ai[l]*ai[l],tree[now].sumy2=bi[l]*bi[l];

        return;

    }

    tree[now].mid=l+r>>;

    build(now<<,l,tree[now].mid);

    build(now<<|,tree[now].mid+,r);

    updata(now);

}

inline void pushdown(int now)

{

    if(tree[now].if_3)

    {

        tree[now].if_3=false;

        tree[now<<].updata3(tree[now].flagx3,tree[now].flagy3);

        tree[now<<|].updata3(tree[now].flagx3,tree[now].flagy3);

    }

    if(tree[now].flagx2||tree[now].flagy2)

    {

        tree[now<<].updata2(tree[now].flagx2,tree[now].flagy2);

        tree[now<<|].updata2(tree[now].flagx2,tree[now].flagy2);

        tree[now].flagx2=,tree[now].flagy2=;

    }

}

void operation1(int now,int l,int r)

{

    if(tree[now].l>=l&&tree[now].r<=r)

    {

        Sumx+=tree[now].sumx,Sumy+=tree[now].sumy;

        Sumx2+=tree[now].sumx2,Sumy2+=tree[now].sumy2;

        Sumxy+=tree[now].sumxy;return;

    }

    if(tree[now].if_3||tree[now].flagx2||tree[now].flagy2) pushdown(now);

    if(l<=tree[now].mid) operation1(now<<,l,r);

    if(r>tree[now].mid) operation1(now<<|,l,r);

}

void operation2(int now,int l,int r,double s,double t)

{

    if(tree[now].l>=l&&tree[now].r<=r)

    {

        tree[now].updata2(s,t);

        return;

    }

    if(tree[now].if_3||tree[now].flagx2||tree[now].flagy2) pushdown(now);

    if(l<=tree[now].mid) operation2(now<<,l,r,s,t);

    if(r>tree[now].mid) operation2(now<<|,l,r,s,t);

    updata(now);

}

void operation3(int now,int l,int r,double s,double t)

{

    if(tree[now].l>=l&&tree[now].r<=r)

    {

        tree[now].updata3(s,t);

        return;

    }

    if(tree[now].if_3||tree[now].flagx2||tree[now].flagy2) pushdown(now);

    if(l<=tree[now].mid) operation3(now<<,l,r,s,t);

    if(r>tree[now].mid) operation3(now<<|,l,r,s,t);

    updata(now);

}

int main()

{

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

    for(int i=;i<=n;i++) scanf("%lf",&ai[i]);

    for(int i=;i<=n;i++) scanf("%lf",&bi[i]);

    build(,,n);

    int op,l,r;double s,t;

    while(m--)

    {

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

        if(op==)

        {

            Sumx=,Sumy=,Sumxy=,Sumx2=,Sumy2=;

            operation1(,l,r);

            double size=r-l+,x_=Sumx/size,y_=Sumy/size;

            double a=Sumxy-Sumy*x_-Sumx*y_+y_*x_*size;

            double b=Sumx2-*Sumx*x_+x_*x_*size;

            printf("%.10lf\n",a/b);

        }

        if(op==) scanf("%lf%lf",&s,&t),operation2(,l,r,s,t);

        if(op==) scanf("%lf%lf",&s,&t),operation3(,l,r,s,t);

    }

    return ;

}