蒟蒻莫名0分但是样例过了,在线求助!!!
  • 板块P1471 方差
  • 楼主Liyuqiao11
  • 当前回复3
  • 已保存回复3
  • 发布时间2023/11/6 14:05
  • 上次更新2023/11/6 17:35:43
查看原帖
蒟蒻莫名0分但是样例过了,在线求助!!!
648772
Liyuqiao11楼主2023/11/6 14:05
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
#define int long long
int n,m;
double a[N];
struct T{
    int l;
    int r;
    double sum;
    double num;
    double lazy;
}t[N*4];
void pushup(int i){
    t[i].sum=t[i*2].sum+t[i*2+1].sum;
    t[i].num=t[i*2].num+t[i*2+1].num;
}
void pushdown(int i){
    if(t[i].lazy==0) return;
    if(t[i].l==t[i].r){
        t[i].lazy=0;
        return;
    }
    t[i*2].lazy+=t[i].lazy;
    t[i*2+1].lazy+=t[i].lazy;
    t[i*2].num+=t[i*2].sum*t[i*2].lazy*2+t[i*2].lazy*t[i*2].lazy*(t[i*2].r-t[i*2].l+1);
    t[i*2+1].num+=t[i*2+1].sum*t[i*2+1].lazy*2+t[i*2+1].lazy*t[i*2+1].lazy*(t[i*2+1].r-t[i*2+1].l+1);
    t[i*2].sum+=(t[i*2].r-t[i*2].l+1)*t[i].lazy;
    t[i*2+1].sum+=(t[i*2+1].r-t[i*2+1].l+1)*t[i].lazy;
    t[i].lazy=0;
}
void build(int i,int l,int r){
    t[i].l=l;
    t[i].r=r;
    if(l==r){
        t[i].sum=a[l];
        t[i].num=a[l]*a[l];
        return;
    }
    int mid=(l+r)/2;
    build(i*2,l,mid);
    build(i*2+1,mid+1,r);
    pushup(i);
}
void update(int i,int l,int r,double x){
    if(t[i].l>=l&&t[i].r<=r){
        t[i].num=t[i].num+t[i].sum*x*2+x*x*(t[i].r-t[i].l+1);
        t[i].sum+=(t[i].r-t[i].l+1)*x;
        return;
    }
    pushdown(i);
    if(t[i*2].r>=l){
        update(i*2,l,r,x);
    }
    if(t[i*2+1].l<=r){
        update(i*2+1,l,r,x);
    }
    pushup(i);
}
double query(int i,int l,int r){
    double ans=0;
    if(t[i].l>=l&&t[i].r<=r){
        return t[i].sum;
    }
    pushdown(i);
    if(t[i*2].r>=l){
        ans+=query(i*2,l,r);
    }
    if(t[i*2+1].l<=r){
        ans+=query(i*2+1,l,r);
    }
    return ans;
}
double query2(int i,int l,int r){
    double ans=0;
    if(t[i].l>=l&&t[i].r<=r){
        return t[i].num;
    }
    pushdown(i);
    if(t[i*2].r>=l){
        ans+=query2(i*2,l,r);
    }
    if(t[i*2+1].l<=r){
        ans+=query2(i*2+1,l,r);
    }
    return ans;
}
signed main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    build(1,1,n);
    int op;
    for(int i=1;i<=m;i++){
        int x,y;
        double k;
        cin>>op;
        if(op==1){
            cin>>x>>y>>k;
            update(1,x,y,k);
        }
        if(op==2){
            cin>>x>>y;
            double ans=query(1,x,y)/(double)(y-x+1);
            printf("%.4lf\n",ans);
        }
        if(op==3){
            cin>>x>>y;
            double dc=query2(1,x,y),f=query(1,x,y);
            double av=f/(double)(y-x+1);
            double ans=(double)(dc-f*av*2+av*av*(y-x+1))/(double)(y-x+1);
            printf("%.4lf\n",ans);
        }
    }
    return 0;
}
2023/11/6 14:05
加载中...