BZOJ4821: [Sdoi2017]相关分析【线段树】

4821: [Sdoi2017]相关分析

【题目描述】

传送门

【题解】

将题目中的公式分解得

\large \frac{\sum(x_iy_i-xxy_i-yyx_i+xxyy)}{\sum(x_i^2-xxx_i+xx^2)}

分子拆开得到\sum x_iy_i-xx<em>yy</em>(r-l+1)

分母拆开得到\sum x_i^2-xx^2*(r-l+1)

所以我们可以维护\sum x,\sum y,\sum x_iy_i,\sum x_i^2就可以了

代码如下

#include<cstdio>
using namespace std;
typedef double LL;
const int MAXN=100005;
int n,m,X[MAXN],Y[MAXN];
struct Tree{
    LL Sumx,Sumy,Sumxx,Sumxy,Addx,Addy,Cor,l,r;
    LL get1(){return (l+r)*(r-l+1)/2;}
    LL Cal(LL x){return x*(x+1)/2*(2*x+1)/3;}
    LL get2(){return Cal(r)-Cal(l-1);}
}Tre[MAXN<<2];
void AD(Tree &x,Tree y,Tree z){
    x.Sumx=y.Sumx+z.Sumx,x.Sumy=y.Sumy+z.Sumy;
    x.Sumxx=y.Sumxx+z.Sumxx,x.Sumxy=y.Sumxy+z.Sumxy;
}
void PushUp(int rt){AD(Tre[rt],Tre[rt<<1],Tre[rt<<1|1]);}
void Build(int rt,int L,int R){
    if(L==R){Tre[rt]=(Tree){X[L],Y[L],(LL)X[L]*X[L],(LL)X[L]*Y[L],0ll,0ll,0ll,L,R};return;}
    int mid=(R+L)>>1;
    Build(rt<<1,L,mid);Build(rt<<1|1,mid+1,R);
    PushUp(rt);Tre[rt].l=L,Tre[rt].r=R;
}
void PushDown_Cover(int x){
    Tre[x].Sumx=Tre[x].Sumy=Tre[x].get1();
    Tre[x].Sumxx=Tre[x].Sumxy=Tre[x].get2();
    Tre[x].Addx=Tre[x].Addy=0;Tre[x].Cor=1;
}
void PushDown_Add(int x,LL Addx,LL Addy){
    LL Ln=Tre[x].r-Tre[x].l+1;
    Tre[x].Sumxy+=Addx*Tre[x].Sumy+Addy*Tre[x].Sumx+Addx*Addy*Ln;
    Tre[x].Sumxx+=Addx*Tre[x].Sumx*2+Addx*Addx*Ln;
    Tre[x].Sumx+=Addx*Ln;Tre[x].Sumy+=Addy*Ln;
    Tre[x].Addx+=Addx;Tre[x].Addy+=Addy;
}
void PushDown(int x){
    if(Tre[x].Cor) PushDown_Cover(x<<1),PushDown_Cover(x<<1|1),Tre[x].Cor=0;
    if(Tre[x].Addx||Tre[x].Addy) PushDown_Add(x<<1,Tre[x].Addx,Tre[x].Addy),PushDown_Add(x<<1|1,Tre[x].Addx,Tre[x].Addy),Tre[x].Addx=Tre[x].Addy=0;
}
void Insert(int rt,int L,int R,int l,int r,LL Addx,LL Addy){
    if(l<=L&&R<=r){PushDown_Add(rt,Addx,Addy);return;}
    PushDown(rt);int mid=(R+L)>>1;
    if(l<=mid) Insert(rt<<1,L,mid,l,r,Addx,Addy);
    if(mid<r) Insert(rt<<1|1,mid+1,R,l,r,Addx,Addy);
    PushUp(rt);
}
void Cover(int rt,int L,int R,int l,int r){
    if(l<=L&&R<=r){PushDown_Cover(rt);return;}
    PushDown(rt);int mid=(R+L)>>1;
    if(l<=mid) Cover(rt<<1,L,mid,l,r);
    if(mid<r) Cover(rt<<1|1,mid+1,R,l,r);
    PushUp(rt);
}
Tree Query(int rt,int L,int R,int l,int r){
    if(l<=L&&R<=r) return Tre[rt];
    PushDown(rt);int mid=(R+L)>>1;Tree ret;
    ret=(Tree){0ll,0ll,0ll,0ll,0ll,0ll,0ll,0ll,0ll};
    if(l<=mid) AD(ret,ret,Query(rt<<1,L,mid,l,r));
    if(mid<r) AD(ret,ret,Query(rt<<1|1,mid+1,R,l,r));
    return ret;
}
#include<cctype>
int read(){
    int ret=0;char ch=getchar();bool f=1;
    for(;!isdigit(ch);ch=getchar()) f^=!(ch^'-');
    for(; isdigit(ch);ch=getchar()) ret=(ret*10+ch-48);
    return f?ret:-ret;
}
int main(){
    n=read(),m=read();
    for(int i=1;i<=n;i++) X[i]=read();
    for(int i=1;i<=n;i++) Y[i]=read();
    Build(1,1,n);
    for(int i=1;i<=m;i++){
        int typ=read(),L=read(),R=read(),x,y;
        if(typ==1){
            Tree ret=Query(1,1,n,L,R);int Len=R-L+1;
            double ret1=(double)ret.Sumxy-(double)ret.Sumx*ret.Sumy/Len;
            double ret2=(double)ret.Sumxx-(double)ret.Sumx*ret.Sumx/Len;
            printf("%.10lf\n",ret1/ret2);
        }else{
            x=read(),y=read();
            if(typ==3) Cover(1,1,n,L,R);
            Insert(1,1,n,L,R,x,y);
        }
    }
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注

开始在上面输入您的搜索词,然后按回车进行搜索。按ESC取消。

返回顶部