N为什么要开到3e5+15?
  • 板块P1471 方差
  • 楼主lrj3247
  • 当前回复3
  • 已保存回复3
  • 发布时间2024/12/17 21:53
  • 上次更新2024/12/18 14:48:50
查看原帖
N为什么要开到3e5+15?
983702
lrj3247楼主2024/12/17 21:53

RT

#include <bits/stdc++.h>
#define ld long double
using namespace std;
const int N = 3e5+15;//N改到1e5+15会RE,求问为什么
struct Node{
	ld sum1,sum2,tag;
	int l,r,len;
	Node(){
		sum1=sum2=tag=0;
		l = r = len = 0;
	}
};
int n,m;
ld a[N];
struct SegmentTree{
	Node tr[N<<2];
	void pushdown(Node &rt,Node &ls,Node &rs){
		if(rt.tag!=0){
			ls.tag+=rt.tag;
			ls.sum2+=(ls.len*rt.tag*rt.tag)+2*ls.sum1*rt.tag;
			ls.sum1+=ls.len*rt.tag;
			rs.tag+=rt.tag;
			rs.sum2+=(rs.len*rt.tag*rt.tag)+2*rs.sum1*rt.tag;
			rs.sum1+=rs.len*rt.tag;
			rt.tag=0;
		}
		return ;
	}
	void update(Node &rt,Node ls,Node rs){
		rt.sum1=ls.sum1+rs.sum1;
		rt.sum2=ls.sum2+rs.sum2;
		return ;
	}
	void build(int id,int l,int r){
		tr[id].l=l,tr[id].r=r,tr[id].len = r-l+1;
		if(l==r){
			tr[id].sum1=a[l];
			tr[id].sum2=a[l]*a[l];
			return ;
		}
		int mid = l+r>>1;
		build(id<<1,l,mid);
		build(id<<1|1,mid+1,r);
		update(tr[id],tr[id<<1],tr[id<<1|1]);
	}
	void change(int id,int x,int y,int l,int r,ld k){
		if(x<=l&&r<=y){
			tr[id].tag+=k;
			tr[id].sum2 += (tr[id].len*k*k)+2*tr[id].sum1*k;
			tr[id].sum1 += (tr[id].len)*k;
			return ;
		}
		pushdown(tr[id],tr[id<<1],tr[id<<1|1]);
		int mid = l+r>>1;
		if(x<=mid) change(id<<1,x,y,l,mid,k);
		if(y>mid) change(id<<1|1,x,y,mid+1,r,k);
		update(tr[id],tr[id<<1],tr[id<<1|1]);
	}
	Node Query(int id,int x,int y,int l,int r){
		int mid = l+r>>1;
		pushdown(tr[id],tr[id<<1],tr[id<<1|1]); 
		if(x<=l&&r<=y) return tr[id];
		if(y<=mid) return Query(id<<1,x,y,l,mid);
		if(x>mid) return Query(id<<1|1,x,y,mid+1,r);
		Node ret;
		update(ret,Query(id<<1,x,y,l,mid),Query(id<<1|1,x,y,mid+1,r));
		return ret;
	}
}T;
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>n>>m;
	for(int i = 1 ; i<=n ; i++) cin>>a[i];
	T.build(1,1,n);
	for(int i = 1 ; i<=m ; i++){
		int op,x,y;
		cin>>op>>x>>y;
		if(op==1){
			ld k;
			cin>>k;
			T.change(1,x,y,1,n,k);
		}
		if(op==2){
			Node tmp = T.Query(1,x,y,1,n);
			long double ans = tmp.sum1*1.0/(y-x+1);
			cout<<fixed<<setprecision(4)<<ans<<"\n";
		}
		if(op==3){
			Node tmp = T.Query(1,x,y,1,n);
			ld pjs = tmp.sum1/(y-x+1);
			ld ans = tmp.sum2/(y-x+1)-(pjs*pjs);
			cout<<fixed<<setprecision(4)<<ans<<"\n";
		}
	}
	return 0;
}
2024/12/17 21:53
加载中...