蒟蒻求助线段树方差
  • 板块P1471 方差
  • 楼主eggegg185
  • 当前回复3
  • 已保存回复3
  • 发布时间2022/8/19 16:38
  • 上次更新2023/10/27 14:35:10
查看原帖
蒟蒻求助线段树方差
676055
eggegg185楼主2022/8/19 16:38

我在写这个线段树题的时候写寄了,通过下数据发现,add之前的方差正常,平均数正常,但add之后的方差就寄了,蒟蒻怀疑是add和pushdown的问题,但是由于太蒻没看出来,请问有没有大佬帮蒟蒻看看qwq

#include <iostream>
#include <iomanip>
using namespace std;
int n;
struct tree {
    double a[400001];
    double sum[400001];
    double square[400001];
    double lazy[400001];
    void pushup(int k) {
        sum[k] = sum[k*2]+sum[k*2+1];
        square[k] = square[k*2]+square[k*2+1];
    }
    void build(int k = 1,int l = 1,int r = n) {
        if(l == r) {
            sum[k] = a[l];
            square[k] = a[l]*a[l];
            return ;
        }
        int mid = (l+r)>>1;
        build(k*2,l,mid);
        build(k*2+1,mid+1,r);
        pushup(k);
    }
    void pushdown(int k,int l,int r) {
        int mid = (l+r)>>1;
        int c = lazy[k];
        square[k*2] += (mid-l+1)*c*c+2*c*sum[k*2];
        square[k*2+1] += (r-mid)*c*c+2*c*sum[k*2+1];
        sum[k*2] += lazy[k]*(mid-l+1);
        sum[k*2+1] += lazy[k]*(r-mid);
        lazy[k*2] += lazy[k];
        lazy[k*2+1] += lazy[k];
        lazy[k] = 0;
    }
    double getsum(int x,int y,int k = 1,int l = 1,int r = n) {
        if(x <= l && r <= y) {
            return sum[k];
        }
        int mid = (l+r)>>1;
        if(lazy[k]) pushdown(k,l,r);
        pushup(k);
        double ans = 0;
        if(x <= mid) ans += getsum(x,y,k*2,l,mid);
        if(y > mid) ans += getsum(x,y,k*2+1,mid+1,r);
        return ans;
    }
    double getsquare(int x,int y,int k = 1,int l = 1,int r = n) {
        if(x <= l && r <= y) {
            return square[k];
        }
        int mid = (l+r)>>1;
        if(lazy[k]) pushdown(k,l,r);
        pushup(k);
        double ans = 0;
        if(x <= mid) ans += getsquare(x,y,k*2,l,mid);
        if(y > mid) ans += getsquare(x,y,k*2+1,mid+1,r);
        return ans;
    }
    void add(int x,int y,double c,int k = 1,int l = 1,int r = n) {
        if(x <= l && r <= y) {
            lazy[k] += c;
            square[k] += c*c*(r-l+1)+2*c*sum[k];
            sum[k] += (r-l+1)*c;
            return;
        }
        pushdown(k,l,r);
        int mid = (l+r)>>1;
        if(x <= mid) add(x,y,c,k*2,l,mid);
        if(y > mid) add(x,y,c,k*2+1,mid+1,r);
        pushup(k);
    }
    double getaver(int l,int r) {
        return getsum(l,r)/((r-l+1)*1.0);
    }
    double getvar(int l,int r) {
        double bom = getaver(l,r);
        bom *= bom;
        double bim = getsquare(l,r)/((r-l+1)*1.0);
        return bim-bom;
    }
}tres;
int main() {
    int m;
    cin >> n >> m;
    for(int i = 1; i <= n; i++) {
        cin >> tres.a[i];
    }
    tres.build();
    while(m--) {
        int op;
        cin >> op;
        if(op == 1) {
            int x,y;
            double c;
            cin >> x >> y >> c;
            tres.add(x,y,c);
        }
        if(op == 2) {
            int x,y;
            cin >> x >> y;
            cout << fixed << setprecision(4) << tres.getaver(x,y) << endl;
        }
        if(op == 3) {
            int x,y;
            cin >> x >> y;
            cout << fixed << setprecision(4) << tres.getvar(x,y) << endl;
        }
    }
    return 0;
}
2022/8/19 16:38
加载中...