P1471 方差

呜呜呜,挺有教训的一题,下次一定仔细看括号!!!

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+500;
struct Tree{
    int l,r,len;
    double sum;
    double lazy;
}_tr[N<<2],__tr[N<<2];//一个维护区间和,另外一个维护区间平方和.

double w[N];

void pushup(int u)
{
    _tr[u].sum=_tr[u<<1].sum+_tr[u<<1|1].sum;
    __tr[u].sum=__tr[u<<1].sum+__tr[u<<1|1].sum;
}

void pushdown(int u)
{
    __tr[u<<1].lazy+=__tr[u].lazy;
    __tr[u<<1|1].lazy+=__tr[u].lazy;
    __tr[u<<1].sum+=_tr[u<<1].sum*2*__tr[u].lazy+__tr[u<<1].len*__tr[u].lazy*__tr[u].lazy;
    __tr[u<<1|1].sum+=_tr[u<<1|1].sum*2*__tr[u].lazy+__tr[u<<1|1].len*__tr[u].lazy*__tr[u].lazy;
    _tr[u<<1].lazy+=_tr[u].lazy;
    _tr[u<<1|1].lazy+=_tr[u].lazy;
    _tr[u<<1].sum+=_tr[u].lazy*_tr[u<<1].len;
    _tr[u<<1|1].sum+=_tr[u].lazy*_tr[u<<1|1].len;
    _tr[u].lazy=__tr[u].lazy=0;
}

void add(int u,int l,int r,double val)
{
    if(l>_tr[u].r||r<_tr[u].l)    return;
    if(_tr[u].l>=l&&_tr[u].r<=r)
    {
        __tr[u].lazy+=val;
        __tr[u].sum+=_tr[u].sum*2*val+_tr[u].len*val*val;
        _tr[u].lazy+=val;
        _tr[u].sum+=val*_tr[u].len;
        return;
    }pushdown(u);
    add(u<<1,l,r,val);
    add(u<<1|1,l,r,val);
    pushup(u);
}

double query(Tree tree[],int u,int l,int r)
{
    if(l>tree[u].r||r<tree[u].l)    return 0;
    if(l<=tree[u].l&&tree[u].r<=r)  return tree[u].sum;
    pushdown(u);
    return query(tree,u<<1,l,r)+query(tree,u<<1|1,l,r);
}

void build(int u,int l,int r)
{
    _tr[u].l=l,_tr[u].r=r;
    __tr[u].l=l,__tr[u].r=r;
    _tr[u].len=__tr[u].len=(r-l+1);
    _tr[u].lazy=__tr[u].lazy=0;
    if(l==r)
    {
        _tr[u].sum=w[l];
        __tr[u].sum=w[l]*w[l];
        return;
    }int mid=(l+r)>>1;
    build(u<<1,l,mid);
    build(u<<1|1,mid+1,r);
    pushup(u);
}

int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)   scanf("%lf",&w[i]);
    build(1,1,n);
    int op,x,y;
    double k;
    while(m--)
    {
        scanf("%d",&op);
        if(op==1)
        {
            scanf("%d%d%lf",&x,&y,&k);
            add(1,x,y,k);
        }
        else if(op==2)
        {
            scanf("%d%d",&x,&y);
            printf("%.4f\n",query(_tr,1,x,y)/(y-x+1));
        }
        else
        {
            scanf("%d%d",&x,&y);
            double age=query(_tr,1,x,y)/(y-x+1);
            printf("%.4f\n",fabs(age*age-query(__tr,1,x,y)/(y-x+1)));
        }
    }
    return 0;
}