P3707 0pts 悬关
  • 板块灌水区
  • 楼主OrientDragon
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/12/15 12:18
  • 上次更新2024/12/15 16:15:13
查看原帖
P3707 0pts 悬关
1173109
OrientDragon楼主2024/12/15 12:18
#include<bits/stdc++.h>
#define int __int128
#define ls x<<1
#define rs x<<1|1
#define db long double
using namespace std;

const int N=100005;
db X[N],Y[N];

struct SegTree{
	int l,r;
	db sumx,sumy,sumxy,sumxqr,s,t;
	bool cover;
	#define l(x) tree[x].l
	#define r(x) tree[x].r
	#define sumx(x) tree[x].sumx
	#define sumy(x) tree[x].sumy
	#define sumxy(x) tree[x].sumxy
	#define sumxqr(x) tree[x].sumxqr
	#define s(x) tree[x].s
	#define t(x) tree[x].t
	#define cover(x) tree[x].cover
	SegTree(){l=r=sumx=sumy=sumxy=sumxqr=s=t=cover=0;} 
}tree[N<<3];

void pushup(int x){
	sumx(x)=sumx(ls)+sumx(rs);
	sumy(x)=sumy(ls)+sumy(rs);
	sumxy(x)=sumxy(ls)+sumxy(rs);
	sumxqr(x)=sumxqr(ls)+sumxqr(rs);
}

void build(int x,int l,int r){
	if(l==r){
		l(x)=r(x)=l;
		sumx(x)=X[l];
		sumy(x)=Y[l];
		sumxy(x)=X[l]*Y[l];
		sumxqr(x)=X[l]*X[l];
		return;
	}
	int mid=l+r>>1;
	build(ls,l,mid);
	build(rs,mid+1,r);
	l(x)=l,r(x)=r;
	pushup(x);
}

void lzy(int x,db S,db T){
	db l=l(x),r=r(x);
	s(x)+=S,t(x)+=T;
	sumxy(x)+=sumx(x)*T+sumy(x)*S+S*T*(r-l+1);
	sumxqr(x)+=2*S*sumx(x)+S*S*(r-l+1);
	sumx(x)+=S*(r-l+1);
	sumy(x)+=T*(r-l+1);
}

db sqrsum(db x){
	return x*(x+1)*(2*x+1)/6;
}

void rebuild(int x){
	db l=l(x),r=r(x);
	cover(x)=1,s(x)=0,t(x)=0;
	sumx(x)=sumy(x)=(l+r)*(r-l+1)/2;
	sumxqr(x)=sumxy(x)=sqrsum(r)-sqrsum(l-1); 
}

void pushdown(int x){
	if(cover(x)){
		rebuild(ls);
		rebuild(rs);
		cover(x)=0;
	}
	lzy(ls,s(x),t(x));
	lzy(rs,s(x),t(x));
	s(x)=t(x)=0;
}

void modify1(int x,int askl,int askr,db S,db T){
	int l=l(x),r=r(x);
	if(askl<=l&&r<=askr){
		lzy(x,S,T);
		return;
	}
	pushdown(x);
	int mid=l+r>>1;
	if(askl<=mid)modify1(ls,askl,askr,S,T);
	if(askr>mid)modify1(rs,askl,askr,S,T);
	pushup(x);
}

void modify2(int x,int askl,int askr,db S,db T){
	int l=l(x),r=r(x);
	if(askl<=l&&r<=askr){
		rebuild(x);
		lzy(x,S,T);
		return;		
	}
	pushdown(x);
	int mid=l+r>>1;
	if(askl<=mid)modify2(ls,askl,askr,S,T);
	if(askr>mid)modify2(rs,askl,askr,S,T);
	pushup(x);
}

SegTree query(int x,int askl,int askr){
	int l=l(x),r=r(x);
	if(askl<=l&&r<=askr)return tree[x];
	SegTree ret;
	int mid=l+r>>1;
	if(askl<=mid){
		SegTree tmp=query(ls,askl,askr);
		ret.sumx+=tmp.sumx;
		ret.sumy+=tmp.sumy;
		ret.sumxy+=tmp.sumxy;
		ret.sumxqr+=tmp.sumxqr;
	}
	if(askr>mid){
		SegTree tmp=query(rs,askl,askr);
		ret.sumx+=tmp.sumx;
		ret.sumy+=tmp.sumy;
		ret.sumxy+=tmp.sumxy;
		ret.sumxqr+=tmp.sumxqr;
	}
	return ret;
}

signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cout<<fixed<<setprecision(10);
	int n,m,opt,l,r;
	db s,t;
	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--){
		cin>>opt>>l>>r;
		if(opt==1){
			SegTree o=query(1,l,r);
			db x=o.sumx,y=o.sumy,xy=o.sumxy,xx=o.sumxqr;
			// cout<<x<<' '<<y<<' '<<xy<<' '<<xx<<' ';
			cout<<((xy-x*y/(r-l+1))/(xx-x*x/(r-l+1)))<<endl;
		}
		else{
			cin>>s>>t;
			if(opt==2)modify1(1,l,r,s,t);
			else modify2(1,l,r,s,t);
		}
	}
}

直角

2024/12/15 12:18
加载中...