全Wa,求调
  • 板块P1471 方差
  • 楼主xiarui1
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/8/14 18:47
  • 上次更新2024/8/14 20:57:32
查看原帖
全Wa,求调
743593
xiarui1楼主2024/8/14 18:47
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define lson (cur*2)
#define rson (cur*2+1)
#define nlen(p) (segt[p].r-segt[p].l+1)
const int N=100010;
const double eps=1e-9;
int n,q,op,u,v;
double w,a[N];
struct node{
	int l,r;
	double val,tag,pri;
}segt[N*4]; 

void pushup(int cur){
	segt[cur].val=segt[lson].val+segt[rson].val;
	segt[cur].pri=segt[lson].pri+segt[rson].pri;
}
void pushdown(int cur){
	if(segt[cur].tag<eps){
		segt[lson].pri+=2*segt[cur].tag*segt[lson].val+segt[cur].tag*segt[cur].tag*nlen(lson);
		segt[lson].val+=segt[cur].tag*nlen(lson);
		segt[lson].tag+=segt[cur].tag;
		segt[rson].pri+=2*segt[cur].tag*segt[rson].val+segt[cur].tag*segt[cur].tag*nlen(rson);
		segt[rson].val+=segt[cur].tag*nlen(rson);
		segt[rson].tag+=segt[cur].tag;		
		segt[cur].tag=0;
	}
}
void maketree(int cur, int l, int r){
	segt[cur].l=l;
	segt[cur].r=r;
	if(l==r){
		segt[cur].val=a[l];
		segt[cur].pri=a[l]*a[l];
		return;
	}
	int mid=(l+r)/2;
	maketree(lson,l,mid);
	maketree(rson,mid+1,r);
	pushup(cur);
}
double query(int cur, int l, int r){
	if(l <= segt[cur].l and segt[cur].r <= r){
		return segt[cur].val;
	}
	int mid=(segt[cur].l+segt[cur].r)/2;
	pushdown(cur);
	double res=0;
	if(l<=mid) res+=query(lson,l,r);
	if(mid+1<=r) res+=query(rson,l,r);
	return res;
}
double query1(int cur, int l, int r){
	if(l <= segt[cur].l and segt[cur].r <= r){
		return segt[cur].pri;
	}
	int mid=(segt[cur].l+segt[cur].r)/2;
	pushdown(cur);
	double res=0;
	if(l<=mid) res+=query1(lson,l,r);
	if(mid+1<=r) res+=query1(rson,l,r);
	return res;
}
void modify(int cur,int l,int r,double delta){
	if(l <= segt[cur].l and segt[cur].r <=r){
		segt[cur].tag+=delta;
		segt[cur].pri+=2*delta*segt[cur].val+delta*delta*nlen(cur);
		segt[cur].val+=delta*nlen(cur);
		return;
	}
	int mid=(segt[cur].l+segt[cur].r)/2;
	pushdown(cur);
	if(l<=mid) modify(lson,l,r,delta);
	if(mid+1<=r) modify(rson,l,r,delta);
	pushup(cur);
}
signed main(){
	cin>>n>>q;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	maketree(1,1,n);
	for(int i=1;i<=q;i++){
		cin>>op>>u>>v;
		if(op==1){
			cin>>w;
			modify(1,u,v,w);
		}else if(op==2){
			cout<<fixed<<setprecision(4)<<query(1,u,v)*1.0/(v-u+1)<<endl;
		}else{
		//	cout<<query(1,u,v)<<" "<<query1(1,u,v)<<endl;
			cout<<fixed<<setprecision(4)<<query1(1,u,v)*1.0/(v-u+1)-(query(1,u,v)*1.0/(v-u+1))*(query(1,u,v)*1.0/(v-u+1))<<endl;
		}
	}
	return 0;
}
2024/8/14 18:47
加载中...