70pts TLE求调(马蜂良好)
  • 板块P1471 方差
  • 楼主SANJIAOJIE
  • 当前回复3
  • 已保存回复3
  • 发布时间2025/1/23 19:11
  • 上次更新2025/1/23 21:54:37
查看原帖
70pts TLE求调(马蜂良好)
1074157
SANJIAOJIE楼主2025/1/23 19:11
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n,t;
double lzy[N*4];
double a[N],w[N*4];
void pushup(int u){
	w[u]=w[u*2]+w[u*2+1];
}
//建树 
void build(int u,int L,int R){
	if(L==R){
		w[u]=a[L];return;
	}
	int M=(L+R)/2;
	build(u*2,L,M);
	build(u*2+1,M+1,R);
	pushup(u);
}
//[L,R]是否被[l,r]包含 
bool InRange(int L,int R,int l,int r){
	return (l<=L)&&(R<=r);
}
//有无重叠区间 
bool OutoRange(int L,int R,int l,int r){
	return (L>r)||(R<l);
}
//标记 
void maketag(int u,int len,double x){
	lzy[u]+=x; //修改当前结点延长标记 
	w[u]+=len*x; //修改当前结点延区间和
}
//下传 
void pushdown(int u,int L,int R){
	int M=(L+R)/2;
	maketag(u*2,M-L+1,lzy[u]);
	maketag(u*2+1,R-M,lzy[u]);
	lzy[u]=0; //避免重复 
}
//区间查询 
double query(int u,int L,int R,int l,int r){
	if(InRange(L,R,l,r))return w[u];
	if(!OutoRange(L,R,l,r)){
		int M=(L+R)/2;
		pushdown(u,L,R);
		return query(u*2,L,M,l,r)+query(u*2+1,M+1,R,l,r);
	}
	else return 0;
}
//区间修改
void update(int u,int L,int R,int l,int r,double x){
	if(InRange(L,R,l,r))maketag(u,R-L+1,x);
	else if(!OutoRange(L,R,l,r)){
		int M=(L+R)/2;
		pushdown(u,L,R);
		update(u*2,L,M,l,r,x);
		update(u*2+1,M+1,R,l,r,x);
		pushup(u);
	}
}
int main(){
	std::ios::sync_with_stdio(false);
    std::cin.tie(0);
	cout<<fixed<<setprecision(4);
	cin>>n>>t;
	for(int i=1;i<=n;i++)cin>>a[i];
	build(1,1,n);
	while(t--){
		int q,x,y;
		double k;
		cin>>q;
		if(q==1){
			cin>>x>>y>>k;
			update(1,1,n,x,y,k);
		}else if(q==2){
			cin>>x>>y;
			cout<<1.0*query(1,1,n,x,y)/(y-x+1)<<"\n";
		}else{
			cin>>x>>y;
			double p=1.0*query(1,1,n,x,y)/(y-x+1);
			double q,ans=0;
			for(int i=x;i<=y;i++){
				double r=query(1,1,n,i,i)-p;
				ans=ans+r*r;
			}
			cout<<ans/(y-x+1)<<"\n";
		}
	}
	return 0;
}

2025/1/23 19:11
加载中...