求看代码,不知道为什么0分
  • 板块P1471 方差
  • 楼主owlcatchfish
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/8/1 10:42
  • 上次更新2024/8/1 11:34:19
查看原帖
求看代码,不知道为什么0分
373100
owlcatchfish楼主2024/8/1 10:42
#include<bits/stdc++.h>
#define endl '\n'
#define int long long
#define lc u<<1     //左孩子
#define rc u<<1|1   //右孩子
using namespace std;
const int N=1e5+10;
double w[N];//初始值
struct Tree{
	int l,r;
	double sum,sum2,add;//sum区间值 add懒惰标记
}tr[N*4];
void pushup(int u){//上传
	tr[u].sum=tr[lc].sum+tr[rc].sum;
	tr[u].sum2=tr[lc].sum2+tr[rc].sum2;
}
void pushdown(int u){//下传
	if(tr[u].add){
		int tmp=tr[u].add;
		//注意先修改sum2再修改sum, sum2的更新需要sum值
		tr[lc].sum2+=2*tmp*tr[lc].sum+(tr[lc].r-tr[lc].l+1)*tmp*tmp;
		tr[rc].sum2+=2*tmp*tr[rc].sum+(tr[rc].r-tr[rc].l+1)*tmp*tmp;
		tr[lc].sum+=tmp*(tr[lc].r-tr[lc].l+1);
		tr[rc].sum+=tmp*(tr[rc].r-tr[rc].l+1);
		tr[lc].add+=tmp;
		tr[rc].add+=tmp;
		tr[u].add=0;
	}
}
void change(int u,int x,int y,double k){//区间修改
	if(x>tr[u].r || y<tr[u].l) return;//修改区间与当前区间无交集
	if(x<=tr[u].l && tr[u].r<=y){//当前区间被修改区间完全覆盖
		tr[u].sum2+=2*k*tr[u].sum+(tr[u].r-tr[u].l+1)*k*k;
		tr[u].sum+=(tr[u].r-tr[u].l+1)*k;	
		tr[u].add+=k;
		return;
	}
	pushdown(u);//需要查询下面区间,向下传递懒标记
	change(lc,x,y,k);
	change(rc,x,y,k);
	pushup(u);//向上更新区间值
}
double query1(int u,int x,int y){
	if(x>tr[u].r || y<tr[u].l) return 0;
	if(x<=tr[u].l && tr[u].r<=y) return tr[u].sum;
	pushdown(u);
	return query1(lc,x,y)+query1(rc,x,y);
}
double query2(int u,int x,int y){
	if(x>tr[u].r || y<tr[u].l) return 0;
	if(x<=tr[u].l && tr[u].r<=y) return tr[u].sum2;
	pushdown(u);
	return query2(lc,x,y)+query2(rc,x,y);
}
void build(int u,int l,int r){
	tr[u]={l,r,w[l],w[l]*w[l],0};
	if(l==r) return;
	int m=(l+r)>>1;
	build(lc,l,m);
	build(rc,m+1,r);
	pushup(u);	
}
void solve(){
	int n,m;cin>>n>>m;
	for(int i=1;i<=n;i++) cin>>w[i];
	build(1,1,n);
	while(m--){
		int op,x,y;cin>>op>>x>>y;
		if(op==1){
			double k;cin>>k;
			change(1,x,y,k);
		}
		if(op==2){
			double ave=query1(1,x,y)/(y-x+1);
			double ans=ave;
			printf("%.4lf\n",ans);
		}
		if(op==3){
			double ave=1.0*query1(1,x,y)/(y-x+1);
			double t1=1.0*query2(1,x,y)/(y-x+1);
			double ans=t1-ave*ave;
			printf("%.4lf\n",ans);
		}
	}

}
signed main(){
//	std::ios::sync_with_stdio(false);
//	cin.tie(0);cout.tie(0);
	int T=1;
	while(T--) solve();
	return 0;
}





2024/8/1 10:42
加载中...