社区讨论
求救,只过了样例
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 条回复,欢迎继续交流。
正在加载回复...