30pts求调,悬棺
查看原帖
30pts求调,悬棺
1034667
Elysian_Realme楼主2023/12/19 17:20

rt

// Problem: 
//     P1471 方差
//   
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P1471
// Memory Limit: 125 MB
// Time Limit: 1000 ms

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double dou;
struct node{
	int lef,rit;
	dou sqsum,sum;
	dou tag;
}tree[4000005];
dou n,m;
dou a[1000005];
void pushup(int i){
	tree[i].sum=tree[i*2].sum+tree[i*2+1].sum;
	tree[i].sqsum=tree[i*2].sqsum+tree[i*2+1].sqsum;
}
void pushdown(int i){
	int lc=i*2,rc=i*2+1;
	tree[lc].tag+=tree[i].tag;
	tree[rc].tag+=tree[i].tag;
	tree[lc].sqsum+=(tree[lc].rit-tree[lc].lef+1)*tree[i].tag*tree[i].tag+2*tree[i].tag*tree[lc].sum;
	tree[lc].sum+=(tree[lc].rit-tree[lc].lef+1)*tree[i].tag;
	tree[rc].sqsum+=(tree[rc].rit-tree[rc].lef+1)*tree[i].tag*tree[i].tag+2*tree[i].tag*tree[rc].sum;
	tree[rc].sum+=(tree[rc].rit-tree[rc].lef+1)*tree[i].tag;
	tree[i].tag=0;
}
void build(int i,int l,int r){
	tree[i].lef=l,tree[i].rit=r;
	if(l==r){
		tree[i].sum=a[l];
		tree[i].sqsum=a[l]*a[l];
		return;
	}
	int mid=(l+r)/2;
	build(i*2,l,mid);
	build(i*2+1,mid+1,r);
	pushup(i);
}
void update(int i,int l,int r,dou k){
	if(tree[i].lef==l&&tree[i].rit==r){
		tree[i].tag+=k;
		tree[i].sqsum+=(tree[i].rit-tree[i].lef+1)*k*k+2*k*tree[i].sum;
		tree[i].sum+=(tree[i].rit-tree[i].lef+1)*k;
		return;
	}
	pushdown(i);
	int mid=(tree[i].lef+tree[i].rit)>>1;
	if(mid>=l)
		update(i*2,l,min(mid,r),k);
	if(mid+1<=r)
		update(i*2+1,max(mid+1,l),r,k);
	pushup(i);
}
pair<dou,dou> query(int i,int l,int r){
	if(tree[i].lef==l&&tree[i].rit==r)
		return make_pair(tree[i].sum,tree[i].sqsum);
	pushdown(i);
	pair <dou,dou> ret(0,0);
	int mid=(tree[i].lef+tree[i].rit)>>1;
	pair <dou,dou> a(0,0);
	if(mid>=l){
		a=query(i*2,l,min(mid,r));
		ret.first+=a.first,ret.second+=a.second;
	}
	if(mid+1<=r){
		a=query(i*2+1,max(mid+1,l),r);
		ret.first+=a.first,ret.second+=a.second;
	}
	return ret;
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++)
		cin>>a[i];
	build(1,1,n);
	for(int i=1;i<=m;i++){
		dou op;int x,y;cin>>op>>x>>y;
		if(op==1){
			dou k;cin>>k;
			update(1,x,y,k);
		}else if(op==2){
			pair <dou,dou> a=query(1,x,y);
			dou ans=a.first*1.0/(y-x+1);
			ans*=10000;
			ans+=0.5;
			ans=(int)ans;
			ans/=10000;
			printf("%.4lf\n",ans);
		}else{
			pair <dou,dou> a=query(1,x,y);
			dou bar=a.first*1.0/((y-x+1)*1.0);
			dou ans=a.second*1.0/((y-x+1)*1.0)-pow(bar,2);
			ans*=10000;
			ans+=0.5;
			ans=(int)ans;
			ans/=10000;
			printf("%.4lf\n",ans);
		}
	}
	return 0;
}

2023/12/19 17:20
加载中...