社区讨论

求救,只过了样例

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

讨论操作

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

当前回复
0 条
当前快照
1 份
快照标识符
@lo9tligb
此快照首次捕获于
2023/10/28 17:08
2 年前
此快照最后确认于
2023/11/02 11:02
2 年前
查看原帖
rt。
代码如下:
CPP
#include<stdio.h>
#include<algorithm>
#include<vector>
#include<math.h>
#include<iostream>
using namespace std;
#define db double
const int maxn=1e5+7;
int n,m,bl,l[maxn],r[maxn],pos[maxn];
db addtag[maxn][2],covertag[maxn][2];
db x[maxn],y[maxn],x1[maxn],y2[maxn],xy[maxn],x2[maxn];
#define len (r[i]-l[i]+1)
bool flag[maxn];
void build(){
	bl=sqrt(n);
	for(int i=1;i<=bl;i++) l[i]=r[i-1]+1,r[i]=i*bl;
	if(r[bl]!=n) ++bl,l[bl]=r[bl-1]+1,r[bl]=n;
	for(int i=1;i<=bl;i++){
		for(int j=l[i];j<=r[i];j++){
			pos[j]=i,x1[i]+=x[j],y2[i]+=y[j],xy[i]+=x[j]*y[j],x2[i]+=x[j]*x[j];
		}
	}
}
void cleartag(int q){
	if(flag[q]){
		flag[q]=0;
		for(int i=l[q];i<=r[q];i++){
			x[i]=covertag[q][0]+i;
			y[i]=covertag[q][1]+i;
		}
		covertag[q][0]=covertag[q][1]=0;
	}
	if(addtag[q][0]||addtag[q][1]){
		for(int i=l[q];i<=r[q];i++){
			x[i]+=addtag[q][0];
			y[i]+=addtag[q][1];
		}
		addtag[q][0]=addtag[q][1]=0;
	}
}
void cover(int ll,int rr,db s,db t){
	int ql=pos[ll],qr=pos[rr];
	cleartag(ql),cleartag(qr);
	if(ql==qr){
		for(int i=ll;i<=rr;i++){
			x1[ql]-=x[i]-(s+i);
			y2[ql]-=y[i]-(t+i);
			xy[ql]-=x[i]*y[i]-(s+i)*(t+i);
			x2[ql]-=x[i]*x[i]-(s+i)*(s+i);
			x[i]=s+i,y[i]=t+i;
		}
		return;
	}
	for(int i=ql+1;i<qr;i++){
		x1[i]=s*len+(l[i]+r[i])*len/2;
		y2[i]=t*len+(l[i]+r[i])*len/2;
		xy[i]=len*s*t+(s+t)*(l[i]+r[i])*len/2+r[i]*(r[i]+1)*(2*r[i]+1)/6-l[i]*(l[i]-1)*(2*l[i]-1)/6;
		x2[i]=len*s*s+s*(l[i]+r[i])*len+r[i]*(r[i]+1)*(2*r[i]+1)/6-l[i]*(l[i]-1)*(2*l[i]-1)/6;
		covertag[i][0]=s,covertag[i][1]=t;
		addtag[i][0]=addtag[i][1]=0;
		flag[i]=1;
	}
	for(int i=ll;i<=r[ql];i++){
		x1[ql]-=x[i]-(s+i);
		y2[ql]-=y[i]-(t+i);
		xy[ql]-=x[i]*y[i]-(s+i)*(t+i);
		x2[ql]-=x[i]*x[i]-(s+i)*(s+i);
		x[i]=s+i,y[i]=t+i;
	}
	for(int i=l[qr];i<=rr;i++){
		x1[qr]-=x[i]-(s+i);
		y2[qr]-=y[i]-(t+i);
		xy[qr]-=x[i]*y[i]-(s+i)*(t+i);
		x2[qr]-=x[i]*x[i]-(s+i)*(s+i);
		x[i]=s+i,y[i]=t+i;
	}
}
void update(int ll,int rr,db s,db t){
	int ql=pos[ll],qr=pos[rr];
	cleartag(ql),cleartag(qr);
	if(ql==qr){
		for(int i=ll;i<=rr;i++){
			x1[ql]+=s;
			y2[ql]+=t;
			xy[ql]+=s*t+s*y[i]+t*x[i];
			x2[ql]+=s*s+2*s*x[i];
			x[i]=s+i,y[i]=t+i;
		}
		return;
	}
	for(int i=ql+1;i<qr;i++){
		x1[i]=s*len;
		y2[i]=t*len;
		xy[i]=len*s*t+x[i]*s+y[i]*t;
		x2[i]=len*s*s+2*x[i]*s;
		addtag[i][0]=addtag[i][1]=0;
		flag[i]=1;
	}
	for(int i=ll;i<=r[ql];i++){
		x1[ql]+=s;
		y2[ql]+=t;
		xy[ql]+=s*t+s*y[i]+t*x[i];
		x2[ql]+=s*s+2*s*x[i];
		x[i]=s+i,y[i]=t+i;
	}
	for(int i=l[qr];i<=rr;i++){
		x1[qr]+=s;
		y2[qr]+=t;
		xy[qr]+=s*t+s*y[i]+t*x[i];
		x2[qr]+=s*s+2*s*x[i];
		x[i]=s+i,y[i]=t+i;
	}
}
db query(int ll,int rr){
	db resx=0.0,resy=0.0,resxy=0.0,resx2=0.0;
	int ql=pos[ll],qr=pos[rr];
	cleartag(ql),cleartag(qr);
	if(ql==qr){
		for(int i=ll;i<=rr;i++){
			resx+=x[i];
			resy+=y[i];
			resxy+=x[i]*y[i];
			resx2+=x[i]*x[i];
		}
		return (resxy-resx*resy/(rr-ll+1))/(resx2-resx*resx/(rr-ll+1));
	}
	for(int i=ql+1;i<qr;i++){
		resx+=x1[i];
		resy+=y2[i];
		resxy+=xy[i];
		resx2+=x2[i];
	}
	for(int i=ll;i<=r[ql];i++){
		resx+=x[i];
		resy+=y[i];
		resxy+=x[i]*y[i];
		resx2+=x[i]*x[i];
	}
	for(int i=l[qr];i<=rr;i++){
		resx+=x[i];
		resy+=y[i];
		resxy+=x[i]*y[i];
		resx2+=x[i]*x[i];
	}
	return (resxy-resx*resy/(rr-ll+1))/(resx2-resx*resx/(rr-ll+1));
}
signed main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++) scanf("%lf",&x[i]);
	for(int i=1;i<=n;i++) scanf("%lf",&y[i]);
	build();
	for(int i=1,opt,a,b;i<=m;i++){
		static db c,d;
		scanf("%d",&opt);
		if(opt==1) {
			scanf("%d%d",&a,&b);
			printf("%.10lf\n",query(a,b));
		}
		if(opt==2){
			scanf("%d%d%lf%lf",&a,&b,&c,&d);
			update(a,b,c,d);
		}
		if(opt==3){
			scanf("%d%d%lf%lf",&a,&b,&c,&d);
			cover(a,b,c,d);
		}
	}
	return 0;
}

回复

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

正在加载回复...