线段树 未过样例 玄关qwp
  • 板块P1471 方差
  • 楼主Ayk71200
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/2/23 19:48
  • 上次更新2024/2/23 21:42:46
查看原帖
线段树 未过样例 玄关qwp
853503
Ayk71200楼主2024/2/23 19:48
#include<bits/stdc++.h>
using namespace std;
const int mn=100005;
int m,n;
double res[mn],la[mn*4];
struct tree{
	int l,r,mid,c;
	double sum=0,pf=0;
}t[mn*4];
int ls(int x){
	return x<<1;
}
int rs(int x){
	return x<<1|1;
}
void pushu(int x){
	t[x].pf=t[ls(x)].pf+t[rs(x)].pf;
	t[x].sum=t[ls(x)].sum+t[rs(x)].sum;
}
void build(int p,int l,int r){
la[p]=0;
t[p].l=l;
t[p].r=r;
t[p].mid=((l+r)>>1);
t[p].c=r-l+1;
if(l==r){
	t[p].sum=res[l];
	t[p].pf=res[l];
	return;
}
build(ls(p),l,t[p].mid);
build(rs(p),t[p].mid+1,r);
pushu(p);
}
void f(int x,double zw){
la[x]+=zw;
t[x].pf+=2*zw*t[x].sum+t[x].c*zw*zw;
t[x].sum+=t[x].c*zw;
} 
void pushd(int x){
f(ls(x),la[x]);
f(rs(x),la[x]);	
la[x]=0;
}
void jia(int l,int r,int x,double k){
if(l<=t[x].l&&t[x].r<=r){
	f(x,k);
	return;
} 	
pushd(x);
if(l<=t[x].mid) jia(l,r,ls(x),k);
if(r>t[x].mid) jia(l,r,rs(x),k);	
pushu(x);	
}
double quzh(int l,int r,int x){
if(l<=t[x].l&&t[x].r<=r){
return 	t[x].sum;
}
double ans=0;
pushd(x);
if(l<=t[x].mid) ans+=quzh(l,r,ls(x));
if(r>t[x].mid) ans+=quzh(l,r,rs(x));
return ans;
}
double qupf(int l,int r,int x){
if(l<=t[x].l&&t[x].r<=r){
return 	t[x].pf;
}
double ans=0;
pushd(x);
if(l<=t[x].mid) ans+=qupf(l,r,ls(x));
if(r>t[x].mid) ans+=qupf(l,r,rs(x));
return ans;
}

int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) scanf("%lf",&res[i]);
build(1,1,n);
while(m--){
int tt,x,y;
double z;
scanf("%d",&tt);
if(tt==1){
scanf("%d%d%lf",&x,&y,&z);
jia(x,y,1,z);
}
if(tt==2){
scanf("%d%d",&x,&y);
printf("%.4lf\n",quzh(x,y,1)/(y-x+1));	
}
if(tt==3){
scanf("%d%d",&x,&y);
double sumn=quzh(x,y,1);
double pjss=sumn/(y-x+1);
double pfhh=qupf(x,y,1);
double aira=pfhh-2*pjss*sumn-(y-x+1)*sumn*sumn;
printf("%.4lf\n",aira);
}
}
return 0;}

调不动了。。。

2024/2/23 19:48
加载中...