70pts WA on #2#9#10
  • 板块P1471 方差
  • 楼主Li_Yichen
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/7/29 09:25
  • 上次更新2024/7/29 10:24:09
查看原帖
70pts WA on #2#9#10
930325
Li_Yichen楼主2024/7/29 09:25

知道是精度问题,但是找不到了,警示后人的全部改过了,求大佬救救

#include<bits/stdc++.h>
using namespace std;
#define double long double
#define ls(x) (x << 1)
#define rs(x) ((x << 1) | 1)
struct node{
    int l,r;
    double power;
    double sum;
}tree[1600005];
int n,m;
double a[100005];
double lazysum[1600005],lazypower[1600005];
double len(int x){
    return (tree[x].r - tree[x].l + 1);
}
void pushup(int x){
    tree[x].sum = tree[ls(x)].sum + tree[rs(x)].sum;
    tree[x].power = tree[ls(x)].power + tree[rs(x)].power;
}
void pushdown(int x){
    if(lazysum[x] || lazypower[x]){
        lazypower[ls(x)] += lazypower[x];
        lazypower[rs(x)] += lazypower[x];
        lazysum[ls(x)] += lazysum[x];
        lazysum[rs(x)] += lazysum[x];
        tree[ls(x)].power += 2 * lazypower[x] * tree[ls(x)].sum + len(ls(x)) * lazypower[x] * lazypower[x];
        tree[rs(x)].power += 2 * lazypower[x] * tree[rs(x)].sum + len(ls(x)) * lazypower[x] * lazypower[x];
        tree[ls(x)].sum += lazysum[x] * len(ls(x));
        tree[rs(x)].sum += lazysum[x] * len(rs(x));
        lazysum[x] = 0;
        lazypower[x] = 0;
    }
}
void build(int l,int r,int x){
    tree[x].l = l;
    tree[x].r = r;
    lazypower[x] = 0;
    lazysum[x] = 0;
    if(l == r){
        tree[x].sum = a[l];
        tree[x].power = a[l] * a[l];
        return;
    }
    int mid = (l + r) / 2;
    build(l,mid,ls(x));
    build(mid+1,r,rs(x));
    pushup(x);
}
void update(int ql,int qr,int l,int r,int x,double k){
    if(ql <= l && r <= qr){
        tree[x].power += 2 * k * tree[x].sum + len(x) * k * k;
        tree[x].sum += k * len(x);
        lazypower[x] += k;
        lazysum[x] += k;
        return;
    }
    pushdown(x);
    int mid = (l + r) / 2;
    if(ql <= mid) update(ql,qr,l,mid,ls(x),k);
    if(qr > mid) update(ql,qr,mid+1,r,rs(x),k);
    pushup(x);
}
double querysum(int ql,int qr,int l,int r,int x){
    if(ql <= l && r <= qr){
        return tree[x].sum;
    }
    pushdown(x);
    double ans = 0;
    int mid = (l + r) / 2;
    if(ql <= mid) ans += querysum(ql,qr,l,mid,ls(x));
    if(qr > mid) ans += querysum(ql,qr,mid+1,r,rs(x));
    return ans;
}
double querypower(int ql,int qr,int l,int r,int x){
    if(ql <= l && r <= qr){
        return tree[x].power;
    }
    pushdown(x);
    double ans = 0;
    int mid = (l + r) / 2;
    if(ql <= mid) ans += querypower(ql,qr,l,mid,ls(x));
    if(qr > mid) ans += querypower(ql,qr,mid+1,r,rs(x));
    return ans;
}
int main(){
    cin >> n >> m;
    for(int i=1;i<=n;i++){
        cin >> a[i];
    }
    build(1,n,1);
    while(m--){
        int op,x,y;
        cin >> op >> x >> y;
        if(op == 1){
            double k;
            cin >> k;
            update(x,y,1,n,1,k);
        }else if(op == 2){
            int l = y - x + 1;
            double sum = querysum(x,y,1,n,1);
            cout << fixed << setprecision(4) << sum * 1.0 / l << endl;
        }else{
            double part1 = querypower(x,y,1,n,1) * 1.0 / (y - x + 1.0);
            double part2 = pow(querysum(x,y,1,n,1) * 1.0 / (y - x + 1.0),2.0);
            cout << fixed << setprecision(4) << part1 - part2 << endl;
        }
    }
    return 0;
}
2024/7/29 09:25
加载中...