线段树0pts求助(样例过不了)
查看原帖
线段树0pts求助(样例过不了)
895690
gghack_Nythix楼主2023/8/18 12:46

rt

#include<bits/stdc++.h>
#define lid (id << 1)
#define rid (id << 1) | 1
using namespace std;
struct segmt{
	int id,l,r;
	double lazy,cf,sum;
}tr[5000005];
double a[5000005];
void pushup(int id){
	tr[id].sum = tr[lid].sum + tr[rid].sum;
	tr[id].cf = tr[lid].cf + tr[rid].cf;
}
void pushdown(int id,int l,int r){
	if(tr[id].lazy){
		tr[lid].lazy += tr[id].lazy;
		tr[rid].lazy += tr[id].lazy;
		tr[lid].cf += (r - l + 1) * tr[id].lazy * tr[id].lazy + 2 * tr[id].lazy * tr[id].sum;
		tr[rid].cf += (r - l + 1) * tr[id].lazy * tr[id].lazy + 2 * tr[id].lazy * tr[id].sum;
		tr[lid].sum += (r - l + 1) * tr[id].lazy;
		tr[rid].sum += (r - l + 1) * tr[id].lazy;
		tr[id].lazy = 0;
	}
}
void bulid(int id,int l,int r){
	tr[id].l = l,tr[id].r = r;
	if(l == r){
		tr[id].sum = a[l];
		tr[id].cf = a[l] * a[l];
		return ;
	}
	int mid = (l + r) >> 1;
	bulid(lid,l,mid);bulid(rid,mid + 1,r);
	pushup(id);
}
void change(int id,int l,int r,double val){
	pushdown(id,tr[id].l,tr[id].r);
	if(tr[id].l >= l || tr[id].r <= r){
		tr[id].lazy += val;
		tr[id].cf += (r - l + 1) * val * val + tr[id].sum * val * 2;
		tr[id].sum += (r - l + 1) * val;
		return ;
	}
	int mid = (tr[id].l + tr[id].r) >> 1;
	if(tr[id].l <= mid){
		change(lid,l,r,val);
	}
	if(tr[id].r > mid){
		change(rid,l,r,val);
	}
	pushup(id);
}
int querysum(int id,int l,int r){
	int ret = 0;
	if(tr[id].l >= l || tr[id].r <= r){
		return tr[id].sum;
	}
	int mid = (tr[id].l + tr[id].r) >> 1;
	if(tr[id].l <= mid){
		ret += querysum(lid,l,r);
	}
	if(tr[id].r > mid){
		ret += querysum(rid,l,r);
	}
	return ret;
}
int querypow(int id,int l,int r){
	int ret = 0;
	if(tr[id].l >= l || tr[id].r <= r){
		return tr[id].cf;
	}
	int mid = (tr[id].l + tr[id].r) >> 1;
	if(tr[id].l <= mid){
		ret += querypow(lid,l,r);
	}
	if(tr[id].r > mid){
		ret += querypow(rid,l,r);
	}
	return ret;
}
signed main(){
	int n,m;
	cin >> n >> m;
	for(int i = 1;i <= n;++i){
		cin >> a[i];
	}
	bulid(1,1,n);
	while(m--){
		int op,l,r,val;
		cin >> op >> l >> r;
		if(op == 1){
			cin >> val;
			change(1,l,r,val);
		}
		if(op == 2){
			cout << fixed << setprecision(4) << double(querysum(1,l,r) / (r - l + 1)) << endl;
		}
		if(op == 3){
			double sum = querysum(1,l,r),poww = querypow(1,l,r),ans;
			sum /= (r - l + 1);
			ans = poww / (r - l + 1) - sum * sum;
			cout << fixed << setprecision(4) << ans << endl;
		}
	}
	return 0;
}
2023/8/18 12:46
加载中...