解题报告 P1471 方差

题目内容

P1471

大意：维护一段实数序列，使之支持区间加一个数以及区间平均值和方差的查询

解题思路

平均值的求解非常好想，只需要将区间和除以区间长度即可，但是方差呢？如何维护？先考虑将方差的式子进行展开：

\begin{aligned}
s^2&=\frac{\sum_{i=1}^n(x_i-\bar x)^2}{n}\
&=\frac{\sum_{i=1}^n(x_i^2-2x_i\bar x+\bar x^2)}{n}\
&=\frac{\sum_{i=1}^nx_i^2-2\bar x\sum_{i=1}^nx_i+n\bar x^2}{n}\
\because&\frac{\sum_{i=1}^nx_i}n=\bar x\
s^2&=\frac{\sum_{i=1}^nx_i^2}n-\bar x^2
\end{aligned}

所以我们需要维护两棵线段树，分别是维护 \sum x_i 和 \sum x_i^2，但当我们涉及到区间修改的时候呢？维护平方和的线段树怎么搞？见下：

假设要加上去的数为 d

\begin{aligned}
&\sum_{i=1}^n(x_i+d)^2\
=&\sum_{i=1}^n(x_i^2+2x_id+d^2)\
=&\sum_{i=1}^nx_i^2+2d\sum_{i=1}^nx_i+nd^2
\end{aligned}

对比原来的式子，发现要加上去的是 \displaystyle2d\sum_{i=1}^nx_i+nd^2，注意到这里的 \sum x_i 是修改前的，所以修改的时候要先修改平方和，再修改另一个。

然后这题我式子推错一次，pushdown 写挂一次，看来要多练线段树了，代码里面还有一些要注意的东西：

• 注意所有的数字都是实数，建议使用关闭流同步的 cin
• 每次更新线段树的时候要同时更新两个
• 别把式子抄错

顺便吐槽这个数据里面的浮点数的表现形式，简直令人kfjdljahtiojfeawruiofklnvd

然后就差不多了，代码见下：

#include <iostream>
#include <iomanip>
#include <cmath>
#define L (k<<1)
#define R (L|1)
#define M (i+j>>1)
using namespace std;

const int maxn=1e5+5;
int n,m;
double f1[maxn<<2],f2[maxn<<2],tag[maxn<<2];

void build(int i,int j,int k)
{
    if(i==j)
    {
        cin>>f1[k];
        f2[k]=f1[k]*f1[k];
        return;
    }
    build(i,M,L);
    build(M+1,j,R);
    f1[k]=f1[L]+f1[R];
    f2[k]=f2[L]+f2[R];
    return;
}

void down(int i,int j,int k)
{
    int l1=M-i+1,l2=j-M;
    f2[L]+=2.0*tag[k]*f1[L]+l1*tag[k]*tag[k];
    f2[R]+=2.0*tag[k]*f1[R]+l2*tag[k]*tag[k];
    f1[L]+=tag[k]*l1;
    f1[R]+=tag[k]*l2;
    tag[L]+=tag[k],tag[R]+=tag[k];
    tag[k]=0;
    return;
}

void modify(int i,int j,int l,int r,int k,double d)
{
    if(i>=l && j<=r)
    {
        f2[k]+=2.0*d*f1[k]+(j-i+1)*d*d;
        f1[k]+=(j-i+1)*d;
        tag[k]+=d;
        return;
    }
    if(tag[k])
        down(i,j,k);
    if(l<=M)
        modify(i,M,l,r,L,d);
    if(r>M)
        modify(M+1,j,l,r,R,d);
    f1[k]=f1[L]+f1[R];
    f2[k]=f2[L]+f2[R];
    return;
}

double sum1(int i,int j,int l,int r,int k)
{
    if(i>=l && j<=r)
        return f1[k];
    if(tag[k])
        down(i,j,k);
    double ans=0;
    if(l<=M)
        ans+=sum1(i,M,l,r,L);
    if(r>M)
        ans+=sum1(M+1,j,l,r,R);
    return ans;
}

double sum2(int i,int j,int l,int r,int k)
{
    if(i>=l && j<=r)
        return f2[k];
    if(tag[k])
        down(i,j,k);
    double ans=0;
    if(l<=M)
        ans+=sum2(i,M,l,r,L);
    if(r>M)
        ans+=sum2(M+1,j,l,r,R);
    return ans;
}

inline double avr(int l,int r)
{
    return sum1(1,n,l,r,1)/(r-l+1);
}

inline double fangcha(int l,int r)
{
    double avre=avr(l,r),len=r-l+1;
    return sum2(1,n,l,r,1)/len-avre*avre;
}

int main()
{
    ios::sync_with_stdio(false);
    cin>>n>>m;
    build(1,n,1);
    int t,x,y;
    double k;
    while(m--)
    {
        cin>>t>>x>>y;
        if(t==1)
        {
            cin>>k;
            modify(1,n,x,y,1,k);
        }
        else if(t==2)
            cout<<fixed<<setprecision(4)<<avr(x,y)<<endl;
        else
            cout<<fixed<<setprecision(4)<<fangcha(x,y)<<endl;
    }
}