线段树0pts 悬关求调
查看原帖
线段树0pts 悬关求调
754912
Velya_QiDream楼主2025/7/24 15:43
#include <bits/stdc++.h>
#define int long long
using namespace std;

const int tt=1e5+10;
double a[tt];
double cnt[4*tt],cnt2[4*tt],res[4*tt];

void pushup(int k){
	cnt[k]=cnt[k*2]+cnt[k*2+1];
	cnt2[k]=cnt2[k*2]+cnt2[k*2+1];
}

void js(int k,int l,int r){
	if(l==r){
		cnt[k]=a[l];
		cnt2[k]=a[l]*a[l];
		return ;
	}
	int mid=l+(r-l)/2;
	js((k<<1),l,mid);
	js((k<<1)|1,mid+1,r);
	pushup(k);
}

void solve(int k,int l,int r,double z){
	res[k]+=z;
	cnt2[k]+=2*z*cnt[k]+z*z*(r-l+1);
	cnt[k]+=z*(r-l+1);
}

void pushdown(int k,int l,int r){
	if(!res[k]){
		return ;
	}
	int mid=l+(r-l)/2;
	solve((k<<1),l,mid,res[k]);
	solve((k<<1)|1,mid+1,r,res[k]);
	res[k]=0;
}

void add(int k,int l,int r,int x,int y,int z){
	if(l>y||r<x){
		return ;
	}
	if(l>=x&&r<=y){
		solve(k,l,r,z);
		return ;
	}
	int mid=l+(r-l)/2;
	pushdown(k,l,r);
	add((k<<1),l,mid,x,y,z);
	add((k<<1)|1,mid+1,r,x,y,z);
	pushup(k);
}

double sum(int k,int l,int r,int x,int y){
	if(l>y||r<x){
		return 0;
	}
	if(l>=x&&r<=y){
		return cnt[k];
	}
	int mid=l+(r-l)/2;
	pushdown(k,l,r);
	return sum((k<<1),l,mid,x,y)+sum((k<<1)|1,mid+1,r,x,y);
}

double var(int k,int l,int r,int x,int y){
	if(l>y||r<x){
		return 0;
	}
	if(l>=x&&r<=y){
		return cnt2[k];
	}
	int mid=l+(r-l)/2;
	pushdown(k,l,r);
	return var((k<<1),l,mid,x,y)+var((k<<1)|1,mid+1,r,x,y);
}

signed main(){
	int n,m;
	cin >>n>>m;
	for(int i=1;i<=n;i++){
		cin >>a[i];
	}
	js(1,1,n);
	while(m--){
		int op;
		cin >>op;
		if(op==1){
			int x,y;
            double k;
			cin >>x>>y>>k;
			add(1,1,n,x,y,k);
		}else if(op==2){
			int x,y;
			cin >>x>>y;
			double ans=sum(1,1,n,x,y)/(y-x+1);
			printf("%.4lf\n",ans);
		}else{
			int x,y;
			cin >>x>>y;
			double pj=sum(1,1,n,x,y)/(y-x+1);
			double ans=-pj*pj+var(1,1,n,x,y)/(y-x+1);
			printf("%.4lf\n",ans);
		}
	}
	return 0;
} 
2025/7/24 15:43
加载中...