样例能过,但是0pts,求调
查看原帖
样例能过,但是0pts,求调
1213719
Algorithm_king楼主2024/7/21 16:37
#include<bits/stdc++.h>
#define N 100010
using namespace std;
int n,m;
double w[N];
struct node{
	int l,r;
	double sum1,sum2,add;
}tr[N*4];
void pushup(int u)
{
	tr[u].sum1=tr[u<<1].sum1+tr[u<<1|1].sum1;
	tr[u].sum2=tr[u<<1].sum2+tr[u<<1|1].sum2;
}
void pushdown(int u)
{
	tr[u<<1].sum2+=tr[u].add*(2*tr[u<<1].sum1+(tr[u<<1].r-tr[u<<1].l+1)*tr[u].add);
	tr[u<<1].sum1+=(tr[u<<1].r-tr[u<<1].l+1)*tr[u].add;
	tr[u<<1].add+=tr[u].add;
	tr[u<<1|1].sum2+=tr[u].add*(2*tr[u<<1|1].sum1+(tr[u<<1|1].r-tr[u<<1|1].l+1)*tr[u].add);
	tr[u<<1|1].sum1+=(tr[u<<1|1].r-tr[u<<1|1].l+1)*tr[u].add;
	tr[u<<1|1].add+=tr[u].add;
	tr[u].add=0;
}
void build(int u,int l,int r)
{
	if(l==r) tr[u]=(node){l,r,w[r],w[r]*w[r],0};
	else{
		tr[u].l=l,tr[u].r=r;
		int mid=l+r>>1;
		build(u<<1,l,mid),build(u<<1|1,mid+1,r);
		pushup(u);
	}
}
void modify(int u,int l,int r,double add)
{
	if(tr[u].l>=l&&tr[u].r<=r) 
		{
			tr[u].add+=add;
			tr[u].sum2+=add*(2*tr[u].sum1+(tr[u].r-tr[u].l+1)*add);
			tr[u].sum1+=(tr[u].r-tr[u].l+1)*add;
		}
	else{
		pushdown(u);
		int mid=tr[u].l+tr[u].r>>1;
		if(l<=mid) modify(u<<1,l,r,add);
		if(r>mid) modify(u<<1|1,l,r,add);
		pushup(u);
	}
}
double query1(int u,int l,int r)
{
	if(tr[u].l>=l&&tr[u].r<=r) return tr[u].sum1;
	pushdown(u);
	double ans;
	int mid=tr[u].l+tr[u].r>>1;
	if(l<=mid) ans=query1(u<<1,l,r);
	if(r>mid) ans+=query1(u<<1|1,l,r);
	return ans;
}
double query2(int u,int l,int r)
{
	if(tr[u].l>=l&&tr[u].r<=r) return tr[u].sum2;
	pushdown(u);
	double ans;
	int mid=tr[u].l+tr[u].r>>1;
	if(l<=mid) ans=query2(u<<1,l,r);
	if(r>mid) ans+=query2(u<<1|1,l,r);
	return ans;
}
int main()
{
	int op,x,y;
	double k;
	cin>>n>>m;
	for(int i=1;i<=n;i++) cin>>w[i];
	build(1,1,n);
	while(m--)
		{
			cin>>op>>x>>y;
			if(op==1) 
				{
					cin>>k;
					modify(1,x,y,k);
				}
			else if(op==2) printf("%.4lf\n",query1(1,x,y)/(y-x+1));
			else printf("%.4lf\n",query2(1,x,y)/(y-x+1)-query1(1,x,y)*query1(1,x,y)/((y-x+1)*(y-x+1)));
		}
	return 0;
}
2024/7/21 16:37
加载中...