线段树 70pts 求助,WA #2 #9 #10
  • 板块P1471 方差
  • 楼主NASFsky
  • 当前回复1
  • 已保存回复1
  • 发布时间2023/9/24 14:48
  • 上次更新2023/11/2 18:19:41
查看原帖
线段树 70pts 求助,WA #2 #9 #10
375403
NASFsky楼主2023/9/24 14:48

谢谢各位大佬 qwq

#include<bits/stdc++.h>
#define N 100100
#define ls(x) x<<1
#define rs(x) x<<1|1 
using namespace std;
int n,m;
double a[N],tag[N<<2],sum1[N<<2],sum2[N<<2];
//维护sum(l...r)xi sum(l...r)(xi^2) 
void pushup(int x)
{
	sum1[x]=sum1[ls(x)]+sum1[rs(x)];
	sum2[x]=sum2[ls(x)]+sum2[rs(x)];
} 
void add(int x,int l,int r,double k)
{
	sum2[x]+=2*k*sum1[x]+(r-l+1)*k*k; 
	sum1[x]+=(r-l+1)*k;
	tag[x]+=k;
} 
void pushdown(int x,int l,int r)
{
	if(!tag[x])return;
	int mid=(l+r)>>1;
	add(ls(x),l,mid,tag[x]);
	add(rs(x),mid+1,r,tag[x]);
	tag[x]=0;
}
void build(int x,int l,int r)
{
	if(l==r)
	{
		sum1[x]=a[l];
		sum2[x]=a[l]*a[l];
		return;
	}
	int mid=(l+r)>>1;
	build(ls(x),l,mid);
	build(rs(x),mid+1,r);
	pushup(x);
} 
void update(int x,int l,int r,int p,int q,double k)
{
	if(p<=l&&r<=q)
	{
		add(x,l,r,k);
		return;
	}
	int mid=(l+r)>>1;
	pushdown(x,l,r);
	if(p<=mid)update(ls(x),l,mid,p,q,k);
	if(q>mid)update(rs(x),mid+1,r,p,q,k);
	pushup(x);
}
double query1(int x,int l,int r,int p,int q)
{
	if(p<=l&&r<=q)return sum1[x];
	int mid=(l+r)>>1;
	double res=0;
	pushdown(x,l,r);
	if(p<=mid)res+=query1(ls(x),l,mid,p,q);
	if(q>mid)res+=query1(rs(x),mid+1,r,p,q);
	return res;
}
double query2(int x,int l,int r,int p,int q)
{
	if(p<=l&&r<=q)return sum2[x];
	int mid=(l+r)>>1;
	double res=0;
	pushdown(x,l,r);
	if(p<=mid)res+=query2(ls(x),l,mid,p,q);
	if(q>mid)res+=query2(rs(x),mid+1,r,p,q);
	return res;
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)cin>>a[i];
	build(1,1,n);
	int op,l,r;
	double k;
	while(m--)
	{
		scanf("%d%d%d",&op,&l,&r);
		if(op==1)
		{
			cin>>k;
			update(1,1,n,l,r,k);
		}
		else if(op==2)
		{
			double res=query1(1,1,n,l,r),tot=r-l+1;
//			cout<<res<<" "<<tot<<endl;
			printf("%.4lf\n",res/tot);
		}
		else if(op==3)
		{
//			printf("%d %d\n",query1(1,1,n,l,r),query2(1,1,n,l,r));
			double temp=query1(1,1,n,l,r);
//			cout<<temp<<endl;
			double res=(r-l+1)*query2(1,1,n,l,r)-temp*temp,tot=(r-l+1)*(r-l+1);	   
			printf("%.4lf\n",res/tot);            
		}
	}
}
2023/9/24 14:48
加载中...