简单线段树玄关求条
  • 板块P1471 方差
  • 楼主sjwhsss
  • 当前回复4
  • 已保存回复4
  • 发布时间2025/1/22 21:09
  • 上次更新2025/1/23 08:41:37
查看原帖
简单线段树玄关求条
982518
sjwhsss楼主2025/1/22 21:09

RT,公式推对了,线段树应该没问题,0ptsWA求条

#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5+5;
int n , m;
double t1[maxn<<2] , t2[maxn<<2] , tag[maxn<<2] , a[maxn];
inline int ls(int x){return x<<1;}
inline int rs(int x){return x<<1|1;}
inline void PushUp(int p){t1[p]=t1[ls(p)]+t1[rs(p)],t2[p]=t2[ls(p)]+t2[rs(p)];}
inline void PushDown(int p , int l , int r)
{
	int mid = l + r >> 1;
	t2[ls(p)]+=tag[p]*2.0*t1[ls(p)]+tag[p]*tag[p]*(mid - l + 1);
	t2[rs(p)]+=tag[p]*2.0*t1[rs(p)]+tag[p]*tag[p]*(r - mid);
	t1[ls(p)]+=tag[p]*(mid - l + 1);
	t1[ls(p)]+=tag[p]*(r - mid);
	tag[ls(p)]+=tag[p];
	tag[rs(p)]+=tag[p];
	tag[p]=0;
	return;
}
void Build(int p , int l , int r)
{
	if (l == r){t1[p]=a[l],t2[p]=a[l]*a[l];return;}
	int mid = l + r >> 1;
	Build(ls(p) , l , mid);
	Build(rs(p) , mid + 1 , r);
	PushUp(p);
	return;
}
void Update(int p , int l , int r , int L , int R , double val)
{
	if (L <= l && r <= R)
	{
		t2[p]+=val*2.0*t1[p]+val*val*(r - l + 1);
		t1[p]+=val*(r - l + 1);
		tag[p]+=val;
		return;
	}
	PushDown(p , l , r);
	int mid = l + r >> 1;
	if (L <= mid)Update(ls(p) , l , mid , L , R , val);
	if (R > mid)Update(rs(p) , mid + 1 , r , L , R , val);
	PushUp(p);
	return;
}
double QuerySum(int p , int l , int r , int L , int R)
{
	if (L <= l && r <= R) return t1[p];
	PushDown(p , l , r);
	int mid = l + r >> 1;
	double res = 0;
	if (L <= mid)res+=QuerySum(ls(p) , l , mid , L , R);
	if (R > mid)res+=QuerySum(rs(p) , mid + 1 , r , L , R);
	return res;
}
double QueryPowSum(int p , int l , int r , int L , int R)
{
	if (L <= l && r <= R) return t2[p];
	PushDown(p , l , r);
	int mid = l + r >> 1;
	double res = 0;
	if (L <= mid)res+=QueryPowSum(ls(p) , l , mid , L , R);
	if (R > mid)res+=QueryPowSum(rs(p) , mid + 1 , r , L , R);
	return res;
}
int main ()
{
//	freopen("in.txt" , "r" , stdin);
	scanf("%d%d" , &n , &m);
	for (int i = 1; i <= n; i++)scanf("%lf" , &a[i]);
	Build(1 , 1 , n);
	while(m--)
	{
		int op , l , r;
		double k = 0;
		scanf("%d%d%d" , &op , &l , &r);
		if (op == 1)scanf("%lf" , &k),Update(1 , 1 , n , l , r , k);
		else if (op == 2)printf("%.4lf\n" , QuerySum(1 , 1 , n , l , r) / (r - l + 1));
		else
		{
			double sum = QuerySum(1 , 1 , n , l , r)/(r - l + 1) , len = r - l + 1;
			printf("%.4lf\n" , QueryPowSum(1 , 1 , n , l , r)/len - (sum * sum));
		}
	}
	return 0;
}
2025/1/22 21:09
加载中...