洛谷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
说明
样例说明:
数据规模:
线段树题,维护 区间和值 时再维护一个 区间平方和 。
即:
附代码:
#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;
}