0分求调
  • 板块P1471 方差
  • 楼主aha097
  • 当前回复1
  • 已保存回复1
  • 发布时间2025/7/29 20:01
  • 上次更新2025/7/30 09:47:44
查看原帖
0分求调
1022551
aha097楼主2025/7/29 20:01
//  P1471 方差

#include<bits/stdc++.h>

using namespace std;

class SegTree{
  private:
    int N, h;
    vector<double> Sums, SqSums, lazyS, sizes;

  public:
    SegTree(int n, vector<double> arr){
        N = n;
        h = sizeof(int) * 8 - __builtin_clz(n);
        Sums.assign(2*N, 0.0), SqSums.assign(2*N, 0.0), lazyS.assign(2*N, 0.0), sizes.assign(2*N, 0.0);
        for(int i = 0;i < N;i++){
          Sums[i+N] = arr[i];
          SqSums[i+N] = arr[i] * arr[i];
          sizes[i+N] = 1.0;
        }
        for(int i = N-1;i > 0;i--){
          Sums[i] = Sums[i<<1] + Sums[i<<1|1];
          SqSums[i] = SqSums[i<<1] + SqSums[i<<1|1];
          sizes[i] = sizes[i<<1] + sizes[i<<1|1];
        }
    }

    void apply(int p, double s){
      SqSums[p] += 2.0 * s * Sums[p] + s * s * sizes[p];
      Sums[p] += sizes[p] * s;
      if(p < N) lazyS[p] += s;
    }

    // A more robust push implementation
void push(int p) {
    // Collect ancestors by walking up the tree from p's parent
    vector<int> ancestors;
    for (int i = p >> 1; i > 0; i >>= 1) {
        ancestors.push_back(i);
    }

    // Push lazy tags down from the root by iterating through the collected ancestors in reverse
    for (int i = ancestors.size() - 1; i >= 0; --i) {
        int t = ancestors[i];
        if (lazyS[t] != 0.0) {
            apply(t << 1, lazyS[t]);
            apply(t << 1 | 1, lazyS[t]);
            lazyS[t] = 0.0;
        }
    }
}

    void build(int p){
      while(p > 1){
        p >>= 1;
        Sums[p] = Sums[p<<1] + Sums[p<<1|1];
        SqSums[p] = SqSums[p<<1|1] + SqSums[p<<1];
      }
    }

    void inc(int l, int r, double s){
      int l0 = l + N, r0 = r + N;
      push(l0);
      push(r0-1);
      for(l += N, r += N;l < r;l >>= 1, r >>= 1){
        if(l&1){
          apply(l++, s);
        }
        if(r&1){
          apply(--r, s);
        }
      }
      build(l0);
      build(r0-1);
    }

    double queryAverage(int l, int r){
      double sums = 0.0;
      l += N, r += N;
      int l0 = l, r0 = r;
      push(l);
      push(r-1);
      for(;l < r;l >>= 1, r >>= 1){
        if(l&1) sums += Sums[l++];
        if(r&1) sums += Sums[--r];
      }
      // cout << sums << endl;
      return sums / (1.0 * (r0 - l0));
    }

    double querySD(int l, int r){
      double sqrs = 0;
      double Average = queryAverage(l, r);
      l += N, r += N;
      int l0 = l, r0 = r;
      push(l);
      push(r-1);
      for(;l < r;l >>= 1, r >>= 1){
        if(l&1) sqrs += SqSums[l++];
        if(r&1) sqrs += SqSums[--r];
      }
      return -Average * Average + sqrs / (1.0 * (r0 - l0));
    }
};



int main() {
    int N, M;
    cin >> N >> M;
    vector<double> arr(N, 0);
    for(int i = 0;i < N;i++) cin >> arr[i];
    SegTree seg = SegTree(N, arr);

    cout << setprecision(4) << fixed;
    for(int i = 0;i < M;i++){
      int x, y, z;
      cin >> x >> y >> z;
      if(x == 1){
        double k;
        cin >> k;
        seg.inc(y-1, z, k);
      }
      if(x == 2){
        cout << seg.queryAverage(y-1, z) << "\n";
      }
      if(x == 3){
        cout << seg.querySD(y-1, z) << "\n";
      }
    }
    return 0;
}

2025/7/29 20:01
加载中...