线段树求方差板题求助,双倍经验可AC
  • 板块P1471 方差
  • 楼主紊莫turtle
  • 当前回复3
  • 已保存回复3
  • 发布时间2023/1/20 08:50
  • 上次更新2023/10/24 03:33:05
查看原帖
线段树求方差板题求助,双倍经验可AC
443675
紊莫turtle楼主2023/1/20 08:50

rt,从P2122来的,那题已经AC。
本题已开double。

然而除了样例全WA。

//Author: Velvet on Luogu(uid=443675)
#include <bits/stdc++.h>
#define int long long
#define mkpr make_pair
#define fi first
#define se second
#define F(i,a,b) for(int i=(a);i<=(b);i++)
#define dF(i,a,b) for(int i=(a);i>=(b);i--)
using namespace std;
using namespace __gnu_cxx;
inline int read(){int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f;}
inline void write(int x){if (x < 0) x = ~x + 1, putchar('-');if (x > 9) write(x / 10);putchar(x % 10 + '0');}
inline void writeln(int x){write(x);putchar('\n');}
inline void writesp(int x){write(x);putchar(' ');}
inline int lowbit(int x) {return x&(-x);}
typedef pair<int,int> Pair;
const int N=100005;
int n,m;
double a[N];
struct SegmentTree_sum{
	int l,r,len;
	double sum,tag,sq;
}t[N*4];
void pushup(int p){
	t[p].sq=t[p*2+1].sq+t[p*2].sq;
	t[p].sum=t[p*2+1].sum+t[p*2].sum;
}
void build(int p,int l,int r){
	t[p].l=l,t[p].r=r,t[p].len=r-l+1;
	if(l==r){
		t[p].sum=a[l];t[p].sq=a[l]*a[l];
		return ;
	}
	int mid=(l+r)>>1;
	build(p*2,l,mid);
	build(p*2+1,mid+1,r);
	pushup(p);
}
void spread(int p){
	int q=t[p].tag;
	t[p*2+1].tag+=q; t[p*2].tag+=q;
	t[p*2].sq+=q*2*t[p*2].sum+q*q*t[p*2].len;
	t[p*2+1].sq+=q*2*t[p*2+1].sum+q*q*t[p*2+1].len; 
	t[p*2].sum+=q*t[p*2].len;
	t[p*2+1].sum+=q*t[p*2+1].len;  
	t[p].tag=0;
}
void change(int p,int l,int r,double v){
	if(t[p].l>=l&&t[p].r<=r){
		t[p].tag+=v;
		t[p].sq+=2*v*t[p].sum+v*v*t[p].len;
		t[p].sum+=v*t[p].len;
		return ;
	}
	int mid=(t[p].l+t[p].r)>>1;
	spread(p);
	if(l<=mid) change(p*2,l,r,v);
	if(r>mid) change(p*2+1,l,r,v);
	pushup(p); 
}
double ask1(int p,int l,int r){
	if(t[p].l>=l&&t[p].r<=r)
		return t[p].sum;
	int mid=(t[p].l+t[p].r)>>1,rt=0;
	spread(p);
	if(l<=mid) rt+=ask1(p*2,l,r);
	if(r>mid) rt+=ask1(p*2+1,l,r);
	return rt;
}
double ask2(int p,int l,int r){
	if(t[p].l>=l&&t[p].r<=r)
		return t[p].sq;
	int mid=(t[p].l+t[p].r)>>1,rt=0;
	spread(p);
	if(l<=mid) rt+=ask2(p*2,l,r);
	if(r>mid) rt+=ask2(p*2+1,l,r);
	return rt;
}
double pf(double x){return x*x;}
signed main(){
	ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    cin>>n>>m;
	F(i,1,n) cin>>a[i];
	build(1,1,n);
	F(i,1,m){
		int op,l,r;
		double d;
		cin>>op>>l>>r;
		if(op==1){
			cin>>d;
			change(1,l,r,d);
		}else if(op==2){
			Pair ans=mkpr(ask1(1,l,r),r-l+1);
			cout<<fixed<<setprecision(4)<<(ans.fi*1.0/ans.se)<<endl;
		}else{
			Pair ans=mkpr((r-l+1)*ask2(1,l,r)-pf(ask1(1,l,r)),pf(r-l+1));
			cout<<fixed<<setprecision(4)<<(ans.fi*1.0/ans.se)<<endl;
		}
	}
    return 0;
}

2023/1/20 08:50
加载中...