50pts,AC #3~#7,被卡精度求调
查看原帖
50pts,AC #3~#7,被卡精度求调
477821
toolong114514楼主2024/1/16 21:32
#include<iostream>
using namespace std;
#define int long long
typedef long double db;
const int N=1e6+10;
struct node{
	int l,r,len;
	db xsum,ysum,xysum,x_2sum,lrsum,sum_2,laz1,laz2;
	bool fill;
}tree[4*N];
db x[N],y[N];
inline void push_up(int pos){
	tree[pos].xsum=tree[pos*2].xsum+tree[pos*2+1].xsum;
	tree[pos].ysum=tree[pos*2].ysum+tree[pos*2+1].ysum;
	tree[pos].xysum=tree[pos*2].xysum+tree[pos*2+1].xysum;
	tree[pos].x_2sum=tree[pos*2].x_2sum+tree[pos*2+1].x_2sum;
}
inline void build(int pos,int lft,int rgt){
	tree[pos].l=lft;
	tree[pos].r=rgt;
	tree[pos].len=rgt-lft+1;
	if(lft==rgt){
		tree[pos].xsum=x[lft];
		tree[pos].ysum=y[lft];
		tree[pos].xysum=x[lft]*y[lft];
		tree[pos].x_2sum=x[lft]*x[lft];
		tree[pos].sum_2=db(lft*lft);
		tree[pos].lrsum=db(lft);
		return;
	}
	int mid=(lft+rgt)/2;
	build(pos*2,lft,mid);
	build(pos*2+1,mid+1,rgt);
	push_up(pos);
	tree[pos].sum_2=tree[pos*2].sum_2+tree[pos*2+1].sum_2;
	tree[pos].lrsum=tree[pos*2].lrsum+tree[pos*2+1].lrsum;
}
inline void push_down(int pos){
	if(tree[pos].fill){
		tree[pos].fill=false;
		tree[pos*2].fill=true;
		tree[pos*2+1].fill=true;
		tree[pos*2].laz1=tree[pos*2].laz2=0;
		tree[pos*2+1].laz1=tree[pos*2+1].laz2=0;
		//改积and平方 
		tree[pos*2].xysum=tree[pos*2].x_2sum=tree[pos*2].sum_2;
		tree[pos*2+1].xysum=tree[pos*2+1].x_2sum=tree[pos*2+1].sum_2;
		//改区间和 
		tree[pos*2].xsum=tree[pos*2].ysum=tree[pos*2].lrsum;
		tree[pos*2+1].xsum=tree[pos*2+1].ysum=tree[pos*2+1].lrsum;
	}
	if(tree[pos].laz1||tree[pos].laz2){
		//改区间积和 
		tree[pos*2].xysum+=tree[pos].laz1*tree[pos*2].ysum+tree[pos].laz2*tree[pos*2].xsum+tree[pos*2].len*tree[pos].laz1*tree[pos].laz2;
		tree[pos*2+1].xysum+=tree[pos].laz1*tree[pos*2+1].ysum+tree[pos].laz2*tree[pos*2+1].xsum+tree[pos*2+1].len*tree[pos].laz1*tree[pos].laz2;
		//改平方
		tree[pos*2].x_2sum+=2*tree[pos].laz1*tree[pos*2].xsum+tree[pos*2].len*tree[pos].laz1*tree[pos].laz1;
		tree[pos*2+1].x_2sum+=2*tree[pos].laz1*tree[pos*2+1].xsum+tree[pos*2+1].len*tree[pos].laz1*tree[pos].laz1;
		//改区间和
		tree[pos*2].xsum+=tree[pos].laz1*tree[pos*2].len;
		tree[pos*2].ysum+=tree[pos].laz2*tree[pos*2].len;
		tree[pos*2+1].xsum+=tree[pos].laz1*tree[pos*2+1].len;
		tree[pos*2+1].ysum+=tree[pos].laz2*tree[pos*2+1].len;
		//懒标记
		tree[pos*2].laz1+=tree[pos].laz1;
		tree[pos*2+1].laz1+=tree[pos].laz1;
		tree[pos*2].laz2+=tree[pos].laz2;
		tree[pos*2+1].laz2+=tree[pos].laz2;
		//清空
		tree[pos].laz1=tree[pos].laz2=0;			 
	}	
}
inline void upd1(int pos,int lft,int rgt,db s,db t){
	if(lft<=tree[pos].l&&tree[pos].r<=rgt){
		tree[pos].xysum+=s*tree[pos].ysum+t*tree[pos].xsum+tree[pos].len*s*t;
		tree[pos].x_2sum+=2*s*tree[pos].xsum+tree[pos].len*s*s;
		tree[pos].xsum+=tree[pos].len*s;
		tree[pos].ysum+=tree[pos].len*t;
		tree[pos].laz1+=s;
		tree[pos].laz2+=t;
		return;
	}
	if(rgt<tree[pos].l||tree[pos].r<lft) return;
	push_down(pos);
	upd1(pos*2,lft,rgt,s,t);
	upd1(pos*2+1,lft,rgt,s,t);
	push_up(pos);
}
inline void upd2(int pos,int lft,int rgt){
	if(lft<=tree[pos].l&&tree[pos].r<=rgt){
		tree[pos].xysum=tree[pos].x_2sum=tree[pos].sum_2;
		tree[pos].xsum=tree[pos].ysum=tree[pos].lrsum;
		tree[pos].fill=true;
		tree[pos].laz1=tree[pos].laz2=0.0;
		return;
	}
	if(rgt<tree[pos].l||tree[pos].r<lft) return;
	push_down(pos);
	upd2(pos*2,lft,rgt);
	upd2(pos*2+1,lft,rgt);
	push_up(pos);
}
inline db ask1(int pos,int lft,int rgt){//查积 
	if(lft<=tree[pos].l&&tree[pos].r<=rgt) return tree[pos].xysum;
	if(rgt<tree[pos].l||tree[pos].r<lft) return 0.0;
	push_down(pos);
	return ask1(pos*2,lft,rgt)+ask1(pos*2+1,lft,rgt);
}
inline db ask2(int pos,int lft,int rgt){//查x 
	if(lft<=tree[pos].l&&tree[pos].r<=rgt) return tree[pos].xsum;
	if(rgt<tree[pos].l||tree[pos].r<lft) return 0.0;
	push_down(pos);
	return ask2(pos*2,lft,rgt)+ask2(pos*2+1,lft,rgt);
}
inline db ask3(int pos,int lft,int rgt){
	if(lft<=tree[pos].l&&tree[pos].r<=rgt) return tree[pos].ysum;
	if(rgt<tree[pos].l||tree[pos].r<lft) return 0.0;
	push_down(pos);
	return ask3(pos*2,lft,rgt)+ask3(pos*2+1,lft,rgt);
}
inline db ask4(int pos,int lft,int rgt){
	if(lft<=tree[pos].l&&tree[pos].r<=rgt) return tree[pos].x_2sum;
	if(rgt<tree[pos].l||tree[pos].r<lft) return 0.0;
	push_down(pos);
	return ask4(pos*2,lft,rgt)+ask4(pos*2+1,lft,rgt);
}
int n,m;
signed main(){
	ios::sync_with_stdio(false);
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>x[i];
	}
	for(int i=1;i<=n;i++){
		cin>>y[i];
	}
	build(1,1,n);
	while(m--){
		int op,ll,rr,ss,tt;
		cin>>op>>ll>>rr;
		if(op==1){
			db xy=ask1(1,ll,rr),xx=ask2(1,ll,rr),yy=ask3(1,ll,rr),x2=ask4(1,ll,rr);
			cout<<(xy-(xx*yy)/db(rr-ll+1))/(x2-(xx*xx)/db(rr-ll+1))<<endl;
		}else{
			cin>>ss>>tt;
			if(op==3){
				upd2(1,ll,rr);
				upd1(1,ll,rr,ss,tt); 
			}else{
				upd1(1,ll,rr,ss,tt);
			}
		}
	}
	return 0;
}
2024/1/16 21:32
加载中...