区间加出错,悬三观求调
  • 板块P1471 方差
  • 楼主Z_kazuha
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/8/23 21:01
  • 上次更新2024/8/24 01:16:39
查看原帖
区间加出错,悬三观求调
1419569
Z_kazuha楼主2024/8/23 21:01
#include <bits/stdc++.h>
using namespace std;
const int N=100005;
int ls(int p){return p<<1;}
int rs(int p){return p<<1|1;}
int n,m;
double a[N],sum1[N<<2],tag[N<<2],sum2[N<<2];
void pushup(int p){
	sum1[p]=sum1[ls(p)]+sum1[rs(p)];
	sum2[p]=sum2[ls(p)]+sum2[rs(p)];
}
void build(int p,int pl,int pr){
	if(pl==pr){
		sum1[p]=a[pl];
		sum2[p]=a[pr]*a[pr];
		return;
	}
	int mid=(pl+pr)>>1;
	build(ls(p),pl,mid);
	build(rs(p),mid+1,pr);
	pushup(p);
} 
void addtag(int p,int pl,int pr,double k){
	sum2[p]+=2*k*sum1[p]+(pr-pl+1)*k;
	sum1[p]+=(pr-pl+1)*k;
	tag[p]+=k;
}
void pushdown(int p,int pl,int pr){
	if(tag[p]){
		int mid=(pl+pr)>>1;
		addtag(ls(p),pl,mid,tag[p]);
		addtag(rs(p),mid+1,pr,tag[p]);
		return;
	}
}
void update(int p,int pl,int pr,int L,int R,double k){
	if(pl>=L&&pr>=R){
		addtag(p,pl,pr,k);
		return;	
	}
	int mid=(pl+pr)>>1;
	pushdown(p,pl,pr);
	if(L<=mid)update(ls(p),pl,mid,L,R,k);
	if(R>mid)update(rs(p),mid+1,pr,L,R,k);
	pushup(p);
}
double query(int p,int pl,int pr,int L,int R){
	if(L<=pl&&R>=pr)return sum1[p];
	int mid=(pl+pr)>>1;
	pushdown(p,pl,pr);
	double res=0;
	if(L<=mid)res+=query(ls(p),pl,mid,L,R);
	if(R>mid)res+=query(rs(p),mid+1,pr,L,R);
	pushup(p);
}
double query1(int p,int pl,int pr,int L,int R){
	if(L<=pl&&R>=pr)return sum2[p];
	int mid=(pl+pr)>>1;
	pushdown(p,pl,pr);
	double res=0;
	if(L<=mid)res+=query(ls(p),pl,mid,L,R);
	if(R>mid)res+=query(rs(p),mid+1,pr,L,R);
	pushup(p);
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++)cin>>a[i];
	build(1,1,n);
	for(int i=1;i<=n;i++){
		int o,x,y;
		double k;
		cin>>o;
		if(o==1){
			cin>>x>>y>>k;
			update(1,1,n,x,y,k);
			for(int i=1;i<=n*4;i++)
				cout<<sum1[i]<<" ";
				cout<<endl;
				for(int i=1;i<=n*4;i++)cout<<sum2[i]<<" ";
				cout<<endl;
		}
		else if(o==2){
			cin>>x>>y;
			double res=query(1,1,n,x,y);
			int len=y-x+1;
			cout<<fixed<<setprecision(4)<<res/len<<endl;
		}else{
			cin>>x>>y;
			int len=y-x+1;
			double res=query(1,1,n,x,y);
			res=res/(y-x+1)*(res/len);
			double res1=query1(1,1,n,x,y);
			cout<<fixed<<setprecision(4)<<res1/len-res<<endl;
		}
		
	}
	return 0;
}
2024/8/23 21:01
加载中...