线段树0分求助
  • 板块P1471 方差
  • 楼主Xeqwq
  • 当前回复3
  • 已保存回复3
  • 发布时间2022/4/16 12:53
  • 上次更新2023/10/28 03:37:46
查看原帖
线段树0分求助
229373
Xeqwq楼主2022/4/16 12:53

原题link:P1471
问题分析:操作1即修改有错(自己的分析不一定准确)
谢谢dalao!
如果有脑残错误对不起浪费了您的时间 我致以诚挚道歉
代码:

#include <iostream>
using namespace std;
typedef long long ll;
inline ll lc(ll p){return p<<1;}
inline ll rc(ll p){return (p<<1)|1;}
int n,q;
const int Maxn=1e5+5;
ll a[Maxn],sum[Maxn*4],dat[Maxn*4],tag[Maxn*4];
void pushup(int p)
{
	sum[p]=sum[lc(p)]+sum[rc(p)];
	dat[p]=dat[lc(p)]+dat[rc(p)];
}
void build(int p,int l,int r)
{
	if(l==r)
	{
		sum[p]=a[l];
		dat[p]=a[l]*a[l];
		return;
	}
	int mid=(l+r)>>1;
	build(lc(p),l,mid);
	build(rc(p),mid+1,r);
	pushup(p);
}
void movetag(int p,int l,int r,ll t)
{
	tag[p]+=t;
	dat[p]=dat[p]+2*t*sum[p]+n*t*t;
	sum[p]+=t*(r-l+1);
}
void pushdown(int p,int l,int r)
{
	if(tag[p]==0) return;
	int mid=(l+r)>>1;
	movetag(lc(p),l,mid,tag[p]);
	movetag(rc(p),mid+1,r,tag[p]);
	tag[p]=0;
}
void modify(int p,int l,int r,int ql,int qr,ll d)
{
	if(ql<=l&&r<=qr)
	{
		movetag(p,l,r,d);
		return;
	}
	pushdown(p,l,r);
	int mid=(l+r)>>1;
	if(ql<=mid) modify(lc(p),l,mid,ql,qr,d);
	if(mid<qr) modify(rc(p),mid+1,r,ql,qr,d);
	pushup(p);
}
ll qsum(int p,int l,int r,int ql,int qr)
{
	if(ql<=l&&r<=qr) return sum[p];
	pushdown(p,l,r);
	int mid=(l+r)>>1,res=0;
	if(ql<=mid) res+=qsum(lc(p),l,mid,ql,qr);
	if(mid<qr) res+=qsum(rc(p),mid+1,r,ql,qr);
	return res;
}
ll qdat(int p,int l,int r,int ql,int qr)
{
	if(ql<=l&&r<=qr) return dat[p];
	pushdown(p,l,r);
	int mid=(l+r)>>1,res=0;
	if(ql<=mid) res+=qdat(lc(p),l,mid,ql,qr);
	if(mid<qr) res+=qdat(rc(p),mid+1,r,ql,qr);
	return res;
}
signed main()
{
	scanf("%lld%lld",&n,&q);
	for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
	build(1,1,n);
//	cout<<114514<<endl;
	ll op,x,y,k;
	while(q--)
	{
		scanf("%lld%lld%lld",&op,&x,&y);
		if(op==1)
		{
			scanf("%lld",&k);
			modify(1,1,n,x,y,k);
		}
		else if(op==2)
		{
			double avr=(double)1.0*qsum(1,1,n,x,y)/(y-x+1);
			printf("%.4lf\n",avr);
		}
		else if(op==3)
		{
			double avr=(double)1.0*qsum(1,1,n,x,y)/(y-x+1);
			ll sqrsum=qdat(1,1,n,x,y);
//			cout<<sqrsum<<endl;
			double avr2=(double)1.0*sqrsum/(y-x+1);
			printf("%.4lf\n",avr2-avr*avr);
		}
	}
	return 0;
}
2022/4/16 12:53
加载中...