全wa求助样例能过
查看原帖
全wa求助样例能过
523541
Onana_in_XMFLS楼主2023/7/8 16:30
#include <bits/stdc++.h>
typedef long long LL;
typedef unsigned long long ULL;
typedef long double LD;
#define mem(arr,val) memset((arr),(val),(sizeof(arr)))
const int maxn = 100000+10;
using namespace std;
double a[maxn];
int n,m;
struct tree
{
	double sum,tag;
}tr1[4*maxn],tr2[4*maxn];
void pushup(int x)
{
	tr1[x].sum = tr1[x*2].sum+tr1[x*2+1].sum;
	tr2[x].sum = tr2[x*2].sum+tr2[x*2+1].sum;
}
void pushdown(int x,int l,int r)
{
	int mid = (l+r)/2;
	if(tr2[x].tag)
	{
		tr2[x*2].tag += tr2[x].tag;
		tr2[x*2+1].tag += tr2[x].tag;
		tr2[x*2].sum += tr1[x*2].sum*(tr2[x].tag*2)+(mid-l+1)*(tr2[x].tag*tr2[x].tag);
		tr2[x*2+1].sum += tr1[x*2+1].sum*(tr2[x].tag*2)+(r-mid)*(tr2[x].tag*tr2[x].tag);
		tr2[x].tag = 0;
	}
	if(tr1[x].tag)
	{
		tr1[x*2].tag += tr1[x].tag;
		tr1[x*2+1].tag += tr1[x*2+1].tag;
		tr1[x*2].sum += (mid-l+1)*tr1[x].tag;
		tr1[x*2+1].sum += (r-mid)*tr1[x].tag;
		tr1[x].tag = 0;	
	}
}
void build(int x,int l,int r)
{
	tr1[x].tag = tr2[x].tag = 0;
	if(l == r) tr1[x].sum = a[l],tr2[x].sum = a[l]*a[l];
	else
	{
		int mid = (l+r)/2;
		build(x*2,l,mid);
		build(x*2+1,mid+1,r);
		pushup(x);
	}
}
void update(int l,int r,int lnow,int rnow,double k,int x)
{
	if(l <= lnow && rnow <= r)
	{
		tr1[x].tag += k;
		tr2[x].tag += k;
		tr2[x].sum += tr1[x].sum*(k*2)+(r-l+1)*(k*k);
		tr1[x].sum += (r-l+1)*k;
		return;
	}
	if(tr1[x].tag || tr2[x].tag) pushdown(x,lnow,rnow);
	int mid = (lnow+rnow)/2;
	if(l <= mid) update(l,r,lnow,mid,k,x*2);
	if(mid < r) update(l,r,mid+1,rnow,k,x*2+1);
	pushup(x);
	return;
}
double query(tree tr[],int l,int r,int lnow,int rnow,int x)
{
	if(l <= lnow && rnow <= r) return tr[x].sum;
	pushdown(x,lnow,rnow);
	int mid = (lnow+rnow)/2;
	double ans1 = 0,ans2 = 0;
	if(l <= mid) ans1 = query(tr,l,r,lnow,mid,x*2);
	if(mid < r) ans2 = query(tr,l,r,mid+1,rnow,x*2+1);
	pushup(x);
	return (ans1+ans2);
}
int main(int argc,char *argv[])
{
	scanf("%d%d",&n,&m);
	for(int i = 1;i <= n;++i) scanf("%lf",&a[i]);
	build(1,1,n);
	while(m--)
	{
		int op,x,y;
		scanf("%d%d%d",&op,&x,&y);
		if(op == 1)
		{
			double k;scanf("%lf",&k);
			update(x,y,1,n,k,1);
		}
		else if(op == 2)
			printf("%.4f\n",query(tr1,x,y,1,n,1)/((y-x+1)*1.0));
		else
		{
			double tmp = query(tr1,x,y,1,n,1)/(y-x+1)*1.0;
			printf("%.4f\n",query(tr2,x,y,1,n,1)/((y-x+1)*1.0)-tmp*tmp);
		}
	}
	return 0;
}
2023/7/8 16:30
加载中...