线段树,样例不过,求调!!!!!!!!
  • 板块P1471 方差
  • 楼主YZren
  • 当前回复1
  • 已保存回复1
  • 发布时间2025/1/13 17:17
  • 上次更新2025/1/13 21:24:45
查看原帖
线段树,样例不过,求调!!!!!!!!
1218495
YZren楼主2025/1/13 17:17
#include<bits/stdc++.h>
#define int long long
#define double long double
#define endl "\n"
using namespace std;
const int maxn=1e5+10;
int n,m;
double a[maxn];
struct node{
	int l,r;
	double sum,lazy,ans;
} tree[maxn*4];
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*10+ch-48;ch=getchar();}
	return x*f;
}
inline void up(int id){
	tree[id].ans=tree[id*2].ans+tree[id*2+1].ans;
	tree[id].sum=tree[id*2].sum+tree[id*2+1].sum;
}
inline void down(int id){
	tree[id*2].lazy+=tree[id].lazy;
	tree[id*2].ans+=2*tree[id*2].sum*tree[id].lazy+(tree[id*2].r-tree[id].l+1)*tree[id].lazy*tree[id].lazy;
	tree[id*2].sum+=tree[id].lazy*(tree[id*2].r-tree[id*2].l+1);
	tree[id*2+1].lazy+=tree[id].lazy;
	tree[id*2+1].ans+=2*tree[id*2+1].sum*tree[id].lazy+(tree[id*2+1].r-tree[id*2+1].l+1)*tree[id].lazy*tree[id].lazy;
	tree[id*2+1].sum+=tree[id].lazy*(tree[id*2+1].r-tree[id*2+1].l+1);
	tree[id].lazy=0;
}
inline void build(int id,int l,int r){
	tree[id].l=l; tree[id].r=r;
	if(l==r){
		tree[id].ans=a[l]*a[l];
		tree[id].sum=a[l];
		return ;
	}
	int mid=(l+r)/2;
	build(id*2,l,mid); build(id*2+1,mid+1,r);
	up(id);
}
inline void update(int id,int l,int r,double val){
	if(tree[id].l>r||tree[id].r<l) return ;
	if(tree[id].l>=l&&tree[id].r<=r){
		tree[id].lazy+=val;
		tree[id].ans+=val*val*(tree[id].r-tree[id].l+1)+2*val*tree[id].sum;
		tree[id].sum+=val*(tree[id].r-tree[id].l+1);
	}
	if(tree[id].lazy!=0) down(id);
	update(id*2,l,r,val); update(id*2,l,r,val);
	up(id);
}
inline double ask_sum(int id,int l,int r){
	if(tree[id].l>r||tree[id].r<l) return 0;
	if(tree[id].l>=l&&tree[id].r<=r) return tree[id].sum;
	if(tree[id].lazy!=0) down(id);
	return (ask_sum(id*2,l,r)+ask_sum(id*2+1,l,r));
}
inline double ask_ans(int id,int l,int r){
	if(tree[id].l>r||tree[id].r<l) return 0;
	if(tree[id].l>=l&&tree[id].r<=r) return tree[id].ans;
	if(tree[id].lazy!=0) down(id);
	return (ask_ans(id*2,l,r)+ask_ans(id*2+1,l,r));
}
inline double ask(int l,int r,int opt){
	double sum=ask_sum(1,l,r),ans=ask_ans(1,l,r);
	double average=sum/(r-l+1);
	if(opt==2) return average;
	else return (ans+average*average-2*average*sum)/(r-l+1);
}
inline void work(){
	n=read(); m=read();
	for(int i=1;i<=n;i++) a[i]=read();
	build(1,1,n);
	while(m--){
		int opt=read(),l=read(),r=read(),val;
		if(opt==1) val=read(),update(1,l,r,val);
		else cout<<fixed<<setprecision(4)<<ask(l,r,opt)<<endl;
	}
}
signed main(){work();return 0;}
2025/1/13 17:17
加载中...