社区讨论

50分求助!!调了2天了

P3707[SDOI2017] 相关分析参与者 1已保存回复 0

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
0 条
当前快照
1 份
快照标识符
@lobzuxcg
此快照首次捕获于
2023/10/30 05:39
2 年前
此快照最后确认于
2023/11/04 10:55
2 年前
查看原帖
有没有大佬可以帮我看一下哪里错了,或者恰好有 50 分到 100 分的大佬分享一下经验?
万分感谢!!!
CPP
#include<bits/stdc++.h>
using namespace std;
const int N=100005;
struct Tree{
	int l,r,opt[3];
	double len,sumx,sumy,sumxy,sumxx,tag1[3],tag2[3];
}tr[N*4];
//sumx:x的和   sumy: y的和    sumxy:xi*yi的和  sumxx:x^2的和  
//tag1[0]和tag2[0] 是Add操作的tag,tag1[1]和tag1[2]是3操作的tag 
int n,m;
double a[N][2];
double calc(double l,double r){
	return 1.0*r*(r+1.0)*(r*2.0+1.0)/6.0-1.0*l*(l+1.0)*(l*2.0+1.0)/6.0;
}
void push_up(int p){
	int ls=p<<1,rs=p<<1|1;
	tr[p].sumx=tr[ls].sumx+tr[rs].sumx;
	tr[p].sumy=tr[ls].sumy+tr[rs].sumy;
	tr[p].sumxy=tr[ls].sumxy+tr[rs].sumxy;
	tr[p].sumxx=tr[ls].sumxx+tr[rs].sumxx;
}
void update1(int p,double a,double b){
	tr[p].sumxy+=tr[p].len*a*b+b*tr[p].sumx+a*tr[p].sumy;
	tr[p].sumxx+=tr[p].len*a*a+2.0*tr[p].sumx*a;
	tr[p].sumx+=tr[p].len*a;
	tr[p].sumy+=tr[p].len*b;
	tr[p].tag1[0]+=a,tr[p].tag2[0]+=b;tr[p].opt[0]=1;
}
void update2(int p,double a,double b){
	tr[p].sumxy=tr[p].len*a*b+(double)(tr[p].l+tr[p].r)*(a+b)*tr[p].len/2.0+calc((double)(tr[p].l-1),(double)tr[p].r);
	tr[p].sumxx=tr[p].len*a*a+(double)(tr[p].l+tr[p].r)*a*tr[p].len+calc((double)(tr[p].l-1),(double)tr[p].r);
	tr[p].sumx=a*tr[p].len+(double)(tr[p].l+tr[p].r)*tr[p].len/2.0;
	tr[p].sumy=b*tr[p].len+(double)(tr[p].l+tr[p].r)*tr[p].len/2.0;
	tr[p].tag1[1]=a,tr[p].tag2[1]=b;tr[p].opt[1]=1;
}
void push_down(int p){
	if(tr[p].opt[0]==0&&tr[p].opt[1]==0)return;
	int ls=(p<<1),rs=(p<<1|1);
	if(tr[p].opt[1]==1){
		double a=tr[p].tag1[1],b=tr[p].tag2[1];
		update2(ls,a,b);
		update2(rs,a,b);
		tr[p].tag1[1]=tr[p].tag2[1]=0.0;tr[p].opt[1]=0;
	}
	if(tr[p].opt[0]==1){
		double a=tr[p].tag1[0],b=tr[p].tag2[0];
		update1(ls,a,b);
		update1(rs,a,b);
		tr[p].tag1[0]=tr[p].tag2[0]=0.0;tr[p].opt[0]=0;
	}
}
void build(int p,int l,int r){
	tr[p].l=l,tr[p].r=r,tr[p].opt[0]=tr[p].opt[1]=0;tr[p].len=(double)(r-l+1.0);
	tr[p].sumx=tr[p].sumy=tr[p].sumxy=tr[p].sumxx=0;
	tr[p].tag1[0]=tr[p].tag2[0]=tr[p].tag1[1]=tr[p].tag2[1]=0;
	if(l==r){
		tr[p].sumx=a[l][0];
		tr[p].sumy=a[l][1];
		tr[p].sumxy=a[l][0]*a[l][1];
		tr[p].sumxx=a[l][0]*a[l][0];
		return;
	}
	int mid=(l+r)>>1;
	build(p<<1,l,mid);
	build(p<<1|1,mid+1,r);
	push_up(p);
}
void Add(int p,int l,int r,double a,double b){
	if(l<=tr[p].l&&tr[p].r<=r){
		update1(p,a,b);
		return;
	}
	push_down(p);
	int mid=(tr[p].l+tr[p].r)>>1;
	if(l<=mid)Add(p<<1,l,r,a,b);
	if(r>mid)Add(p<<1|1,l,r,a,b);
	push_up(p);
}
void change(int p,int l,int r,double a,double b){
	if(l<=tr[p].l&&tr[p].r<=r){
		update2(p,a,b);
		return;
	}
	push_down(p);
	int mid=(tr[p].l+tr[p].r)>>1;
	if(l<=mid)change(p<<1,l,r,a,b);
	if(r>mid)change(p<<1|1,l,r,a,b);
	push_up(p);
}
Tree query(int p,int l,int r){
	if(l<=tr[p].l&&tr[p].r<=r)return tr[p];
	push_down(p);
	int mid=(tr[p].l+tr[p].r)>>1;
	if(l<=mid&&r>mid){
		Tree res,res1=query(p<<1,l,r),res2=query(p<<1|1,l,r);
		res.sumx=res1.sumx+res2.sumx;
		res.sumy=res1.sumy+res2.sumy;
		res.sumxx=res1.sumxx+res2.sumxx;
		res.sumxy=res1.sumxy+res2.sumxy;
		return res;
	}
	else if(l<=mid)return query(p<<1,l,r);
	else if(r>mid)return query(p<<1|1,l,r);
}
int main(){
//	freopen("1.in","r",stdin);
//	freopen("1.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
		scanf("%lf",&a[i][0]);
	for(int i=1;i<=n;i++)
		scanf("%lf",&a[i][1]);
	build(1,1,n);
	for(int i=1;i<=m;i++){
		int opt,l,r;
		scanf("%d%d%d",&opt,&l,&r);
		if(opt==1){
			double len=(double)(r-l+1);
			Tree res=query(1,l,r);
			double x=res.sumx/len,y=res.sumy/len;
			double ans=(res.sumxy-y*res.sumx-x*res.sumy+len*x*y);
			ans/=(res.sumxx+len*x*x-2.0*x*res.sumx);
//			printf("%.7lf %.7lf %.7lf %.7lf ",res.sumx,res.sumy,res.sumxx,res.sumxy);
			printf("%.7lf\n",ans);
		}
		else if(opt==2){
			double a,b;
			scanf("%lf%lf",&a,&b);
			Add(1,l,r,a,b);
		}
		else{
			double a,b;
			scanf("%lf%lf",&a,&b);
			change(1,l,r,a,b);
		}
	}
	return 0;
}

回复

0 条回复,欢迎继续交流。

正在加载回复...