欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

洛谷P1471 方差

程序员文章站 2022-03-22 13:12:02
...

题目背景

滚粗了的HansBug在收拾旧数学书,然而他发现了什么奇妙的东西。

题目描述

蒟蒻HansBug在一本数学书里面发现了一个神奇的数列,包含N个实数。他想算算这个数列的平均数和方差。

输入输出格式

输入格式:

第一行包含两个正整数N、M,分别表示数列中实数的个数和操作的个数。

第二行包含N个实数,其中第i个实数表示数列的第i项。

接下来M行,每行为一条操作,格式为以下两种之一:

操作1:1 x y k ,表示将第x到第y项每项加上k,k为一实数。

操作2:2 x y ,表示求出第x到第y项这一子数列的平均数。

操作3:3 x y ,表示求出第x到第y项这一子数列的方差。

输出格式:

输出包含若干行,每行为一个实数,即依次为每一次操作2或操作3所得的结果(所有结果四舍五入保留4位小数)。

输入输出样例

输入样例#1:
5 5
1 5 4 2 3
2 1 4
3 1 5
1 1 1 1
1 2 2 -1
3 1 5
输出样例#1:
3.0000
2.0000
0.8000

说明

洛谷P1471 方差

样例说明:

洛谷P1471 方差

数据规模:

洛谷P1471 方差

线段树题,维护 区间和值 时再维护一个 区间平方和 。

即:洛谷P1471 方差洛谷P1471 方差

附代码:

#include<iostream>
#include<algorithm>
#include<cstdio>
#define LSON rt<<1
#define RSON rt<<1|1
#define DATA(x) a[x].data
#define SIGN(x) a[x].c
#define FC(x) a[x].fc
#define LSIDE(x) a[x].l
#define RSIDE(x) a[x].r
#define WIDTH(x) (RSIDE(x)-LSIDE(x)+1)
#define MAXN 100010
using namespace std;
int n,m;
struct node{
       double data,fc,c;
       int l,r;
}a[MAXN<<2];
void pushup(int rt){
     DATA(rt)=DATA(LSON)+DATA(RSON);
     FC(rt)=FC(LSON)+FC(RSON);
}
void pushdown(int rt){
     if(!SIGN(rt)||LSIDE(rt)==RSIDE(rt))
     return;
     SIGN(LSON)+=SIGN(rt);
     FC(LSON)+=2*SIGN(rt)*DATA(LSON)+WIDTH(LSON)*SIGN(rt)*SIGN(rt);
     DATA(LSON)+=SIGN(rt)*WIDTH(LSON);
     SIGN(RSON)+=SIGN(rt);
     FC(RSON)+=2*SIGN(rt)*DATA(RSON)+WIDTH(RSON)*SIGN(rt)*SIGN(rt);
     DATA(RSON)+=SIGN(rt)*WIDTH(RSON);
     SIGN(rt)=0;
}
void buildtree(int l,int r,int rt){
     int mid;
     LSIDE(rt)=l;
     RSIDE(rt)=r;
     if(l==r){
              cin>>DATA(rt);
              FC(rt)=DATA(rt)*DATA(rt);
              return;
              }
     mid=l+r>>1;
     buildtree(l,mid,LSON);
     buildtree(mid+1,r,RSON);
     pushup(rt);
}
void update(int l,int r,double c,int rt){
     int mid;
     if(l<=LSIDE(rt)&&RSIDE(rt)<=r){
                                    SIGN(rt)+=c;
                                    FC(rt)+=2*c*DATA(rt)+WIDTH(rt)*c*c;
                                    DATA(rt)+=c*WIDTH(rt);
                                    return;
                                    }
     pushdown(rt);
     mid=LSIDE(rt)+RSIDE(rt)>>1;
     if(l<=mid)update(l,r,c,LSON);
     if(mid<r)update(l,r,c,RSON);
     pushup(rt);
}
double query(int l,int r,int rt){
     int mid;
     double ans=0.00000000000000;
     if(l<=LSIDE(rt)&&RSIDE(rt)<=r)
     return DATA(rt);
     pushdown(rt);
     mid=LSIDE(rt)+RSIDE(rt)>>1;
     if(l<=mid)ans+=query(l,r,LSON);
     if(mid<r)ans+=query(l,r,RSON);
     return ans;
}
double queans(int l,int r,int rt){
     int mid;
     double ans=0.00000000000000;
     if(l<=LSIDE(rt)&&RSIDE(rt)<=r)
     return FC(rt);
     pushdown(rt);
     mid=LSIDE(rt)+RSIDE(rt)>>1;
     if(l<=mid)ans+=queans(l,r,LSON);
     if(mid<r)ans+=queans(l,r,RSON);
     return ans;
}
int main(){
    int f,x,y;
    double k;
    scanf("%d%d",&n,&m);
    buildtree(1,n,1);
    while(m--){
               scanf("%d%d%d",&f,&x,&y);
               if(f==1){
                        cin>>k;
                        update(x,y,k,1);
                        }
               if(f==2){
                        double s=query(x,y,1);
                        s/=(double)(y-x+1);
                        printf("%.4lf\n",s);
                        }
               if(f==3){
                        double s,s1=query(x,y,1),s2=queans(x,y,1);
                        s1=s1/(y-x+1);
                        s=(double)s2/(y-x+1)-s1*s1;
                        printf("%.4lf\n",s);
                        }
               }
    return 0;
}