线段树0pts求调
  • 板块P1471 方差
  • 楼主cx2021ghj
  • 当前回复1
  • 已保存回复1
  • 发布时间2024/10/23 15:10
  • 上次更新2024/10/23 17:18:19
查看原帖
线段树0pts求调
893608
cx2021ghj楼主2024/10/23 15:10
#include<bits/stdc++.h>
#define ls p<<1
#define rs p<<1|1 
using namespace std;
struct ghj{
	double sum,lazy;
};
ghj tr1[400009],tr2[400009];
int a[400009],n,m,op;
void pushup(int p){
	tr1[p].sum=tr1[ls].sum+tr1[rs].sum;
	tr2[p].sum=tr2[ls].sum+tr2[rs].sum;
}
void pushdown(int l,int r,int p){
	int mid=(l+r)/2;
	tr2[ls].lazy+=tr2[p].lazy;
	tr2[ls].sum+=tr1[ls].sum*(tr2[p].lazy*2)+(mid-l+1)*(tr2[p].lazy*tr2[p].lazy);
	tr2[rs].lazy+=tr2[p].lazy;
	tr2[rs].sum+=tr1[rs].sum*(tr2[p].lazy*2)+(r-mid)*(tr2[p].lazy*tr2[p].lazy);
	tr2[p].lazy=0;
	tr1[ls].lazy+=tr1[p].lazy;
    tr1[ls].sum+=(mid-l+1)*tr1[p].lazy;
    tr1[rs].lazy+=tr1[p].lazy;
    tr1[rs].sum+=(r-mid)*tr1[p].lazy;	
}
void build(int l,int r,int p=1){
	if(l==r){
		tr1[p].sum=a[l];
		tr2[p].sum=a[l]*a[l];
		return;
	}
	int mid=(l+r)/2;
	build(l,mid,ls);
	build(mid+1,r,rs);
	pushup(p);
}
void update(int l,int r,int x,int y,double z,int p=1){
	if(x<=l && r<=y){
		tr2[p].lazy+=z;
		tr2[p].sum+=tr1[p].sum*(z*2)+(r-l+1)*(z*z);
		tr1[p].lazy+=z;
		tr1[p].sum+=(r-l+1)*z;
		return;
	}
	if(tr1[p].lazy || tr2[p].lazy) pushdown(l,r,p);
	int mid=(l+r)/2;
	if(x<=mid) update(l,mid,x,y,z,ls);
	if(y>mid) update(mid+1,r,x,y,z,rs);
	pushup(p);
}
double query(ghj tree[],int l,int r,int x,int y,int p=1){
	if(x<=l && r<=y) return tree[p].sum;
	int mid=(l+r)/2;
	if(tree[p].lazy) pushdown(l,r,p);
	double ans=0;
	if(x<=mid) ans+=query(tree,l,mid,x,y,ls);
	if(y>mid) ans+=query(tree,mid+1,r,x,y,rs);
	pushup(p);
	return ans;
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++) cin>>a[i];
	build(1,n);
	while(m--){
		cin>>op;
		if(op==1){
			int x,y;
			double z;
			cin>>x>>y>>z;
			update(1,n,x,y,z);
		}
		if(op==2){
			int x,y;
			cin>>x>>y;
			cout<<setprecision(4)<<fixed<<query(tr1,1,n,x,y)/((y-x+1)*1.0)<<'\n';
		}
		if(op==3){
			int x,y;
			cin>>x>>y;
			cout<<setprecision(4)<<fixed<<(query(tr2,1,n,x,y)/((y-x+1)*1.0))-(query(tr1,1,n,x,y)/((y-x+1)*1.0))*(query(tr1,1,n,x,y)/((y-x+1)*1.0))<<'\n';
		}
	}
} 
2024/10/23 15:10
加载中...