线段树0分新人求助
  • 板块P1471 方差
  • 楼主Jacky2009
  • 当前回复7
  • 已保存回复7
  • 发布时间2023/1/10 23:49
  • 上次更新2023/10/24 04:48:45
查看原帖
线段树0分新人求助
499231
Jacky2009楼主2023/1/10 23:49
#include<bits/stdc++.h>
using namespace std;
struct tree{
	double sum,sum2,lazy;
}t[400005];
#define ls now<<1
#define rs now<<1|1
//#define double long double
double li[100005];
void update(int now){
	t[now].sum=t[ls].sum+t[rs].sum;
	t[now].sum2=t[ls].sum2+t[rs].sum2;
}
void pushdown(int now,int l,int r){
		int mid=(l+r)>>1;
		t[ls].lazy+=t[now].lazy;
		t[rs].lazy+=t[now].lazy;
		int llen=mid-l+1,rlen=r-mid;
		t[ls].sum2+=t[ls].sum*2*t[now].lazy+t[now].lazy*t[now].lazy*llen;
		t[ls].sum+=t[now].lazy*llen;
		t[rs].sum2+=t[rs].sum*2*t[now].lazy+t[now].lazy*t[now].lazy*rlen;
		t[rs].sum+=t[now].lazy*rlen;
		t[now].lazy=0;
	
	//	cout<<l<<" "<<r<<" "<<t[now].sum<<" "<<t[now].sum2<<" "<<t[now].lazy<<endl;
}
void build(int l,int r,int now){
	t[now].lazy=0;
	if(l==r){
		t[now].sum=li[l];
		t[now].sum2=li[l]*li[l];
		return;
	}
	int mid=(l+r)>>1;
	build(l,mid,ls);
	build(mid+1,r,rs);
	update(now);
	
}
void change(int l,int r,int now,double v,int x,int y){
	if(x<=l&&r<=y){
		t[now].lazy+=v;	
		t[now].sum2+=(t[now].sum*2*t[now].lazy)+t[now].lazy*t[now].lazy*(r-l+1);
		t[now].sum+=(r-l+1)*t[now].lazy;
		return ;
	}
	if(t[now].lazy)pushdown(now,l,r);
	int mid=(l+r)>>1;
	if(x<=mid)change(l,mid,ls,v,x,y);
	if(y>mid)change(mid+1,r,rs,v,x,y);
	update(now);
}
double ask1(int l,int r,int now,int x,int y){
	if(x<=l&&r<=y){
		return t[now].sum;
	}
	if(t[now].lazy)pushdown(now,l,r);
	int mid=(l+r)>>1;
	double ans=0;
	if(x<=mid)ans+=ask1(l,mid,ls,x,y);
	if(y>mid)ans+=ask1(mid+1,r,rs,x,y);
	update(now);
	return ans;
}
double ask2(int l,int r,int now,int x,int y){
	if(x<=l&&r<=y){
		return t[now].sum2;
	}if(t[now].lazy)pushdown(now,l,r);
	int mid=(l+r)>>1;
	double ans=0;
	if(x<=mid)ans+=ask2(l,mid,ls,x,y);
	if(y>mid)ans+=ask2(mid+1,r,rs,x,y);
	update(now);
	return ans;
}
int op,x,y;
double k;
int n,m;
void print(int l,int r,int now){
	if(l==r){
	//	cout<<l<<" "<<r<<" "<<t[now].sum<<" "<<t[now].sum2<<" "<<t[now].lazy<<endl;
	pushdown(now,l,r);
		cout<<l<<" "<<r<<" "<<t[now].sum<<" "<<t[now].sum2<<" "<<t[now].lazy<<endl;
		return; 
	}
	int mid=(l+r)>>1;
	print(l,mid,ls);
	print(mid+1,r,rs);
	
		cout<<l<<" "<<r<<" "<<t[now].sum<<" "<<t[now].sum2<<" "<<t[now].lazy<<endl;
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++)cin>>li[i];
	build(1,n,1);
//	print(1,n,1);
	for(int i=1;i<=m;i++){
		cin>>op>>x>>y;
		if(op==1){
			cin>>k;
			change(1,n,1,k,x,y);
		}
		else if(op==2){
			double ans=ask1(1,n,1,x,y);
			printf("%.4lf\n",ans/(y-x+1));
		}
		else{
			double ans1=ask1(1,n,1,x,y),ans2=ask2(1,n,1,x,y),ans3=ans1/n;
			double ans=ans3*ans3*(y-x+1)-2*ans3*ans1+ans2;
			ans=ans2/n-ans3*ans3;
			printf("%.4lf\n",ans);
		}
	print(1,n,1);
	}
}

```cpp
2023/1/10 23:49
加载中...