30pts线段树TLE求调
查看原帖
30pts线段树TLE求调
670978
Arc0_FishyFool楼主2025/7/22 12:05
#include <bits/stdc++.h>
using namespace std;
int n,m;
double a[114514];
struct SegTree{
	int l,r;
	double sqr,sum,laz;
}t[114514<<2];
inline void pushup(int x){
	t[x].sqr=t[x<<1].sqr+t[x<<1|1].sqr;
	t[x].sum=t[x<<1].sum+t[x<<1|1].sum;
}
inline void pushdown(int x){
	t[x<<1].laz+=t[x].laz;
	t[x<<1|1].laz+=t[x].laz;
	t[x<<1].sqr+=(double)(t[x<<1].r-t[x<<1].l+1)*t[x].laz*t[x].laz+2*t[x<<1].sum*t[x].laz;
	t[x<<1|1].sqr+=(double)(t[x<<1|1].r-t[x<<1|1].l+1)*t[x].laz*t[x].laz+2*t[x<<1|1].sum*t[x].laz;
	t[x<<1].sum+=(double)(t[x<<1].r-t[x<<1].l+1)*t[x].laz;
	t[x<<1|1].sum+=(double)(t[x<<1|1].r-t[x<<1|1].l+1)*t[x].laz;
	t[x].laz=0.0;
}
inline void build(int x,int l,int r){
	t[x].l=l;
	t[x].r=r;
	if(l==r){
		t[x].sqr=a[l]*a[l];
		t[x].sum=a[l];
		return;
	}
	int mid=(l+r)>>1;
	build(x<<1,l,mid);
	build(x<<1|1,mid+1,r);
	pushup(x);
}
inline void edit(int x,int L,int R,double k){
	int l=t[x].l,r=t[x].r;
	if(l==r){
		t[x].laz+=k;
		t[x].sqr+=(double)(t[x].r-t[x].l+1)*k*k+2*t[x].sum*k;
		t[x].sum+=(double)(t[x].r-t[x].l+1)*k;
		return;
	}
	pushdown(x);
	int mid=(l+r)>>1;
	if(L<=mid) edit(x<<1,L,R,k);
	if(R>mid) edit(x<<1|1,L,R,k);
	pushup(x);
}
inline pair<double,double> query(int x,int L,int R){
	int l=t[x].l,r=t[x].r;
	if(l==r){
		return make_pair(t[x].sum,t[x].sqr);
	}
	pushdown(x);
	int mid=(l+r)>>1;
	pair<double,double> res=make_pair(0.0,0.0);
	if(L<=mid) res=make_pair(res.first+query(x<<1,L,R).first,res.second+query(x<<1,L,R).second);
	if(R>mid) res=make_pair(res.first+query(x<<1|1,L,R).first,res.second+query(x<<1|1,L,R).second);
	pushup(x);
	return res;
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;++i) scanf("%lf",a+i);
	build(1,1,n);
	while(m--){
		double opt,x,y,k;
		scanf("%lf%lf%lf",&opt,&x,&y);
		if(opt==1){
			scanf("%lf",&k);
			edit(1,x,y,k);
		}
		else if(opt==2){
			printf("%.4lf\n",query(1,x,y).first/(y-x+1));
		}
		else{
			pair<double,double> ans=query(1,x,y);
			double avr=ans.first/(y-x+1);
			printf("%.4lf\n",ans.second/(y-x+1)-avr*avr);
		}
	}
	return 0;
}
2025/7/22 12:05
加载中...