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