萌新求助线段树,全部RE,qwq
  • 板块P1471 方差
  • 楼主bovine__kebi
  • 当前回复23
  • 已保存回复23
  • 发布时间2020/4/28 12:03
  • 上次更新2023/11/7 03:47:40
查看原帖
萌新求助线段树,全部RE,qwq
294736
bovine__kebi楼主2020/4/28 12:03
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+5;
struct node
{
	int l,r;
	int sum,pf,alz;
}tree[maxn*4];
int In[maxn];
int n,m;
inline int ls(int i){return i<<1;}
inline int rs(int i){return i<<1|1;}
inline void pushup(int i)
{
	tree[i].sum=tree[ls(i)].sum+tree[rs(i)].sum;
	tree[i].pf=tree[ls(i)].pf+tree[rs(i)].pf;
	return;
 }
inline void pushdown(int i)
{
	int a=tree[i].alz;
	tree[ls(i)].pf+=2*a*tree[ls(i)].sum+(tree[ls(i)].r-tree[ls(i)].l+1)*a*a;
	tree[rs(i)].pf+=2*a*tree[rs(i)].sum+(tree[rs(i)].r-tree[rs(i)].l+1)*a*a;
	tree[ls(i)].alz+=a;
	tree[rs(i)].alz+=a;
	tree[ls(i)].sum+=(tree[ls(i)].r-tree[ls(i)].l+1)*a;
	tree[rs(i)].sum+=(tree[rs(i)].r-tree[rs(i)].l+1)*a;
	tree[i].alz=0;
	return;
 }
inline void build(int i,int l,int r)
{
	tree[i].l=l;tree[i].r=r;
	if(l==r)
	{
		tree[i].sum=In[i];
		tree[i].pf=tree[i].sum*tree[i].sum; 
	}
	int mid=(l+r)>>1;
	build(ls(i),l,mid);
	build(rs(i),mid+1,r);
	pushup(i);
 }
inline void add(int i,int l,int r,double k)
{
	if(tree[i].l>r||tree[i].r<l)return;
	if(tree[i].l>=l&&tree[i].r<=r)
	{
		tree[i].alz+=k;
		tree[i].sum+=k*(tree[i].r-tree[i].l+1);
		tree[i].pf+=2*tree[i].sum*k+k*k*(tree[i].r-tree[i].l+1);
		return;
	}
	pushdown(i);
	if(tree[ls(i)].r>=l)add(ls(i),l,r,k);
	if(tree[rs(i)].l<=r)add(rs(i),l,r,k);
	pushup(i);
 }
inline double get_1(int i,int l,int r)
{
	if(tree[i].l>=l&&tree[i].r<=r)return tree[i].sum;
	pushdown(i);
	double sum=0;
	if(tree[ls(i)].r>=l)sum+=get_1(ls(i),l,r); 
	if(tree[rs(i)].l<=r)sum+=get_1(rs(i),l,r);
	return sum; 
} 
inline double get_2(int i,int l,int r)
{
	if(tree[i].l>=l&&tree[i].r<=r)return tree[i].pf;
	pushdown(i);
	double sum=0;
	if(tree[ls(i)].r>=l)sum+=get_2(ls(i),l,r);
	if(tree[rs(i)].l<=r)sum+=get_2(rs(i),l,r);
	return sum;
}
int main()
{
	scanf("%d %d",&n,&m);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&In[i]);
	}
	build(1,1,n);
	for(int i=1;i<=m;i++)
	{
		int cz;
		scanf("%d",&cz);
		if(cz==1)
		{
			int l,r;double k;
			scanf("%d %d %lf",&l,&r,&k);
			add(1,l,r,k);
		}
		if(cz==2)
		{
			int l,r;
			scanf("%d %d",&l,&r);
			double ave=(double)get_1(1,l,r)/(double)(r-l+1);
			printf("%.4f\n",ave);
		}
		if(cz==3)
		{
			int l,r;
			scanf("%d %d",&l,&r);
			double ave=get_1(1,l,r)/(double)(r-l+1);
			double f_n=get_2(1,l,r)/(double)(r-l+1);
			double ans=f_n-ave*ave;
			printf("%.4f\n",ans); 
		}
	}
	return 0;
}
2020/4/28 12:03
加载中...