全WA求助
  • 板块P1471 方差
  • 楼主陆朱良雨
  • 当前回复0
  • 已保存回复0
  • 发布时间2020/10/17 14:45
  • 上次更新2023/11/5 10:34:51
查看原帖
全WA求助
114154
陆朱良雨楼主2020/10/17 14:45
#include<bits/stdc++.h>
using namespace std;
#define N 100001
#define mid (l+r)/2
#define lson node*2
#define rson node*2+1
struct node{
	double squ,sum,lasy;
}tree[4*N];
int n,m,k,x,y;
double kkk,kk,nmp;
double a[N];
inline void update(int node){
  tree[node].squ=tree[lson].squ+tree[rson].squ;
  tree[node].sum=tree[lson].sum+tree[rson].sum;
}
void build(int node,int l,int r){
	if(l==r){
		tree[node].squ=a[l]*a[l];
		tree[node].sum=a[l];
		return;
	}
	build(lson,l,mid);
	build(rson,mid+1,r);
	update(node);
	//cout<<l<<" "<<r<<" "<<tree[node].squ<<" "<<tree[node].sum<<endl;
}
void pushdown(int node,int l,int r){
	if(!tree[node].lasy) return;
	tree[lson].squ+=tree[lson].sum*2*tree[node].lasy+(mid-l+1)*tree[node].lasy*tree[node].lasy;
	tree[rson].squ+=tree[rson].sum*2*tree[node].lasy+(r-mid  )*tree[node].lasy*tree[node].lasy;
	tree[lson].sum+=(mid-l+1)*tree[node].lasy;
	tree[rson].sum+=(r-mid  )*tree[node].lasy;
	tree[lson].lasy+=tree[node].lasy;
	tree[rson].lasy+=tree[node].lasy;
	tree[node].lasy=0;
}
void add(int node,int l,int r,int ll,int rr,int k){
	if(ll<=l&&r<=rr){
		tree[node].lasy+=k;
		tree[node].squ+=tree[node].sum*2*k+(r-l+1)*k*k;
		tree[node].sum+=(r-l+1)*k;
		return;
	}
	pushdown(node,l,r);
	if(ll<=mid) add(lson,l,mid,ll,rr,k);
	if(rr>mid ) add(rson,mid+1,r,ll,rr,k);
	update(node);
}
double ssum(int node,int l,int r,int ll,int rr){
//	cout<<"#";//
	if(ll<=l&&r<=rr){
		return tree[node].sum;
	}
	double p=0;
	pushdown(node,l,r);
	if(ll<=mid) p+=ssum(lson,l,mid,ll,rr);
	if(rr>mid ) p+=ssum(rson,mid+1,r,ll,rr);
	return p;
}
double ssqu(int node,int l,int r,int ll,int rr){
//	cout<<"&";//
	if(ll<=l&&r<=rr){
		return tree[node].squ;
	}
	double p=0;
	pushdown(node,l,r);
	if(ll<=mid) p+=ssqu(lson,l,mid,ll,rr);
	if(rr>mid ) p+=ssqu(rson,mid+1,r,ll,rr);
	return p;
}
double pow(double x){
	return x*x;
}
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++){
		cin>>k>>x>>y;
		if(k==1){
			cin>>nmp;
		//	cout<<"k="<<k<<endl;
			add(1,1,n,x,y,nmp);
		}
		else if(k==2){
		//	 cout<<"k="<<k<<endl;
			 kk=ssum(1,1,n,x,y);
		//	 cout<<kk<<"*"<<endl;
			 printf("%.4lf\n",kk/(y-x+1));
		}
		else if(k==3){
		//	 cout<<"k="<<k<<endl;
			 kk=ssqu(1,1,n,x,y);
			 kkk=ssum(1,1,n,x,y);
		//	 cout<<kkk<<"* ()"<<kk<<endl;
			printf("%.4lf\n",kk/(y-x+1)-pow(kkk/(y-x+1)));
		}
	}
	return 0;
}
2020/10/17 14:45
加载中...