luogu P1471(线段树)

传送门

题意:

维护区间加区间查询平均数,区间查询方差。

分析:

维护区间平均数非常简单,根据式子(sum_{i=1}^{n}a_ifrac{1}{n})得知,我们只需要维护一个区间和即可。

问题就在于维护方差,我们尝试将方差的式子化简一下:

[frac{(a_1-overline{a})^2+(a_2-overline{a})^2+dots+ (a_n-overline{a})^2}{n} ]

[=frac{a_i^2+a_2^2+dots+a_n^2-2*(a_1-overline{a})-2*(a_2-overline{a})-dots-2*(a_n-overline{a})+n*overline{a}^2}{n} ]

[=frac{sum_{i=1}^{i=n}a_i^2-overline{a}*sum_{i=1}^{i=n}a_i+n*overline{a}^2}{n} ]

[=frac{sum_{i=1}^{i=n}a_i^2}{n}-overline{a}^2 ]

因此,我们发现此时,我们只需要维护一个区间的平方和以及区间的和即可。

而对于区间平方和的维护,我们继续化简式子:

[a_1^2+a_2^2+dots+a_n^2 ]

[(a_1+k)^2+(a_2+k)^2+dots+(a_n+k)^2 ]

[=a_1^2+a_2^2+dots+a_n^2+n*k^2+2*k*(a_1+a_2+dots+a_n) ]

[=sum_{i=1}^{i=n}a_i^2+2*k*sum_{i=1}^{i=n}a_i+n*k^2 ]

因此我们发现,每次区间更新(k)的时候,我们只需要增加(2*k*sum_{i=1}^{i=n}a_i+n*k^2),而这个值我们只需要维护一个区间加就可以完成。

综上,我们直接可以用线段树去大力的维护。

代码:

#include <bits/stdc++.h>
using namespace std;
#define maxn 100005
struct Node{
    double sum,mulsum,lazy;
    int len;
}tr[maxn<<2];
double a[maxn];
void push_up(int rt){
    tr[rt].sum=tr[rt<<1].sum+tr[rt<<1|1].sum;
    tr[rt].mulsum=tr[rt<<1].mulsum+tr[rt<<1|1].mulsum;
}
void push_down(int rt,int l,int r){
    if(tr[rt].lazy){
        tr[rt<<1].mulsum+=tr[rt<<1].len*tr[rt].lazy*tr[rt].lazy+ 2*tr[rt].lazy*tr[rt<<1].sum;
        tr[rt<<1|1].mulsum+=tr[rt<<1|1].len*tr[rt].lazy*tr[rt].lazy+ 2*tr[rt].lazy*tr[rt<<1|1].sum;
        tr[rt<<1].lazy+=tr[rt].lazy;
        tr[rt<<1|1].lazy+=tr[rt].lazy;
        tr[rt<<1].sum+=tr[rt].lazy*tr[rt<<1].len;
        tr[rt<<1|1].sum+=tr[rt].lazy*tr[rt<<1|1].len;
        tr[rt].lazy=0;
    }
}
void build(int l,int r,int rt){
    tr[rt].lazy=0;
    tr[rt].len=r-l+1;
    if(l==r){
        tr[rt].sum=a[l];
        tr[rt].mulsum=a[l]*a[l];
        tr[rt].len=r-l+1;
        return ;
    }
    int mid=(l+r)>>1;
    build(l,mid,rt<<1);
    build(mid+1,r,rt<<1|1);
    push_up(rt);
}
void update(int L,int R,int l,int r,int rt,double add){
    if(L<=l&&R>=r){
        tr[rt].mulsum+=(r-l+1)*add*add+2.0*add*tr[rt].sum;
        tr[rt].sum+=(r-l+1)*add;
        tr[rt].lazy+=add;
        return ;
    }
    int mid=(l+r)>>1;
    push_down(rt,l,r);
    if(L<=mid) update(L,R,l,mid,rt<<1,add);
    if(R>mid) update(L,R,mid+1,r,rt<<1|1,add);
    push_up(rt);
}
double querysum(int L,int R,int l,int r,int rt){
    if(L<=l&&R>=r){
        return tr[rt].sum;
    }
    int mid=(l+r)>>1;
    double res=0;
    push_down(rt,l,r);
    if(L<=mid) res+=querysum(L,R,l,mid,rt<<1);
    if(R>mid) res+=querysum(L,R,mid+1,r,rt<<1|1);
    return res;
}
double querymulsum(int L,int R,int l,int r,int rt){
    if(L<=l&&R>=r){
        return tr[rt].mulsum;
    }
    int mid=(l+r)>>1;
    double res=0;
    push_down(rt,l,r);
    if(L<=mid) res+=querymulsum(L,R,l,mid,rt<<1);
    if(R>mid) res+=querymulsum(L,R,mid+1,r,rt<<1|1);
    return res;
}
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        scanf("%lf",&a[i]);
    }
    build(1,n,1);
    while(m--){
        int opt,l,r;
        double add;
        scanf("%d%d%d",&opt,&l,&r);
        if(opt==1){
            scanf("%lf",&add);
            update(l,r,1,n,1,add);
        }
        else if(opt==2){
            double res=querysum(l,r,1,n,1);
            printf("%.4f
",1.0*res/(r-l+1));
        }
        else{
            double tmp=1.0*querysum(l,r,1,n,1)/(r-l+1);
            double res=1.0*querymulsum(l,r,1,n,1)/(r-l+1);
            res-=tmp*tmp;
            printf("%.4f
",res);
        }
    }
    return 0;
}

原文地址:https://www.cnblogs.com/Chen-Jr/p/11160853.html