题解 P1471 【方差】

· · 题解

为分块助威，把这题贴上分块标签！

Solution

先化简方差公式,ave为平均数

\frac{(x_1-ave)^2+(x_2-ave)^2+…+(x_{n-1}-ave)^2+(x_n-ave)^2}{n}

分配律

\frac{(x_1-ave)^2}{n}+\frac{(x_2-ave)^2}{n}+…+\frac{(x_{n-1}-ave)^2}{n}+\frac{(x_n-ave)^2}{n}

用求和符号框起来

\frac{\sum_{i\in N}[(x_i-\frac{\sum x}{n})^2]}{n}

完全平方和公式

\frac{\sum_{i\in N}[(x_i)^2-\frac{2x_i\sum x}{n}+\frac{(\sum x)^2}{n^2}]}{n}

分配律再拉

\sum_{i\in N}(\frac{(x_i)^2}{n}-\frac{2x_i\sum x}{n^2}+\frac{(\sum x)^2}{n^3})

分配律再拖

\frac{(\sum x)^2}{n^2}+\sum_{i\in N}(\frac{(x_i)^2}{n}-\frac{2x_i\sum x}{n^2})

设k为x的平方和，得到

\frac{(\sum x)^2}{n^2}+(\frac{k}{n}-\frac{2(\sum x)^2}{n^2})

去括号+合并同类项，得

\frac{k}{n}-\frac{(\sum x)^2}{n^2}

数据范围是n\leq 100000所以我们可以用分块分别维护区间平方和及区间和，然后回答即可。

Code

#include<cmath>
#include<cstdio>
#include<cctype>
#include<iostream>
#include<algorithm>
using namespace std;typedef long long LL;
int L[401],R[401],n,q,l,r,opt,x,pos[100010],t;
double d,a[100010],sum[401],add[401],sumaf[401];
inline long long read()
{
    char c;int d=1;long long f=0;
    while(c=getchar(),!isdigit(c))if(c==45)d=-1;f=(f<<3)+(f<<1)+c-48;
    while(c=getchar(),isdigit(c)) f=(f<<3)+(f<<1)+c-48;
    return d*f;
}
inline void write(register long long x)
{
    if(x<0)putchar(45),x=-x;
    if(x>9)write(x/10);
    putchar(x%10+48);
    return;
}
double sqr(double x){return x*x;}
void Add(register int l,register int r,double x)//区间修改
{
    int pl=pos[l],pr=pos[r];
    if(pl==pr)//同块内暴力改
    {
        for(register int i=l;i<=r;i++) sumaf[pl]+=2*a[i]*x+sqr(x),a[i]+=x,sum[pl]+=x;
        return;
    }
    for(register int i=l;i<=R[pl];i++) sumaf[pl]+=2*a[i]*x+sqr(x),a[i]+=x,sum[pl]+=x;
    for(register int i=L[pr];i<=r;i++) sumaf[pr]+=2*a[i]*x+sqr(x),a[i]+=x,sum[pr]+=x;//两边暴力改
    for(register int i=pl+1;i<pr;i++) add[i]+=x;//中间+lazy
    return;
}
double ask(register int l,register int r)//查询区间和/区间长度=平均数
{
    int pl=pos[l],pr=pos[r],len=r-l+1;
    double ans=0;
    if(pl==pr)//同块内暴力求
    {
        for(register int i=l;i<=r;i++) ans+=a[i]+add[pl];
        return ans/1.0/len;
    }
    else
    {
        for(register int i=l;i<=R[pl];i++) ans+=a[i]+add[pl];
        for(register int i=L[pr];i<=r;i++) ans+=a[i]+add[pr];//两边暴力改
        for(register int i=pl+1;i<pr;i++) ans+=sum[i]+add[i]*t;//中间+lazy和sum
        return ans/1.0/len;
    }
}
double askfc(register int l,register int r)
{
    int len=r-l+1,pl=pos[l],pr=pos[r];double ave=0,ans=0,answer=0;
    if(pl==pr)//同一块暴力改
    {
        for(register int i=l;i<=r;i++) ave+=a[i]+add[pl],ans+=sqr(a[i]+add[pl]);
        return ans/len-sqr(ave/len);
    }
    for(register int i=l;i<=R[pl];i++) ave+=a[i]+add[pl],ans+=sqr(a[i]+add[pl]);
    for(register int i=L[pr];i<=r;i++) ave+=a[i]+add[pr],ans+=sqr(a[i]+add[pr]);//两边暴力改
    for(register int i=pl+1;i<pr;i++) ave+=sum[i]+add[i]*t,ans+=sumaf[i]+2*sum[i]*add[i]+t*sqr(add[i]);//中间lazy+sum改
    answer=ans/len-sqr(ave/len);
    return answer;
}
signed main()
{
    freopen("1.txt","r",stdin);
    n=read();q=read();t=(int)sqrt(n)+1;
    for(register int i=1;i<=n;i++) scanf("%lf",a+i);
    for(register int i=1;i<=t;i++) 
    {
        L[i]=R[i-1]+1,R[i]=min(R[i-1]+t,n);
        for(register int j=L[i];j<=R[i];j++) pos[j]=i,sum[i]+=a[j],sumaf[i]+=sqr(a[j]);//预处理
    }
    while(q--)
    {
        opt=read();
        if(opt==1)
        {
            l=read();r=read();scanf("%lf",&d);
            Add(l,r,d);
        }
        if(opt==2)
        {
            l=read();r=read();
            printf("%.4lf\n",ask(l,r));
        }
        if(opt==3)
        {
            l=read();r=read();
            printf("%.4lf\n",askfc(l,r));
        }
    }
}