40pts,救救我吧
  • 板块P1471 方差
  • 楼主ChickyHas
  • 当前回复1
  • 已保存回复1
  • 发布时间2023/8/27 07:24
  • 上次更新2023/11/3 00:58:50
查看原帖
40pts,救救我吧
307211
ChickyHas楼主2023/8/27 07:24
#include <iomanip>
#include <iostream>

using namespace std;

const int N = 1e5 + 1;

struct T {
  double s, t;
} t1[N << 2], t2[N << 2];

double a[N], z;
int n, m, x, y, op;

void Push_up(int i) {
  t1[i].s = t1[i << 1].s + t1[i << 1 | 1].s;
  t2[i].s = t2[i << 1].s + t2[i << 1 | 1].s;
}

void Push_down(int i, int l, int r) {
  int mid = l + r >> 1;
  t2[i << 1].t += t2[i].t, t2[i << 1].s += t1[i << 1].s * t2[i].t * 2 + (mid - i + 1) * t2[i].t * t2[i].t;
  t2[i << 1 | 1].t += t2[i].t, t2[i << 1 | 1].s += t1[i << 1 | 1].s * t2[i].t * 2 + (r - mid) * t2[i].t * t2[i].t;
  t2[i].t = 0;
  t1[i << 1].t += t1[i].t, t1[i << 1].s += (mid - l + 1) * t1[i].t;
  t1[i << 1 | 1].t += t1[i].t, t1[i << 1 | 1].s += (r - mid) * t1[i].t;
  t1[i].t = 0;
}

void Build(int i, int l, int r) {
  if (l == r) {
    t1[i].s = a[l], t2[i].s = a[l] * a[l];
    return;
  }
  int mid = l + r >> 1;
  Build(i << 1, l, mid);
  Build(i << 1 | 1, mid + 1, r);
  Push_up(i);
}

double Query(T t[], int i, int l, int r, int tl, int tr) {
  if (tl <= l && tr >= r) {
    return t[i].s;
  }
  if (t[i].t) {
    Push_down(i, l, r);
  }
  double res = 0;
  int mid = l + r >> 1;
  if (tl <= mid) {
    res += Query(t, i << 1, l, mid, tl, tr);
  }
  if (tr > mid) {
    res += Query(t, i << 1 | 1, mid + 1, r, tl, tr);
  }
  return res;
}

void Update(int i, int l, int r, int tl, int tr, double v) {
  if (tl <= l && tr >= r) {
    t2[i].t += v, t2[i].s += t1[i].s * v * 2 + (r - l + 1) * v * v;
    t1[i].t += v, t1[i].s += (r - l + 1) * v;
    return;
  }
  if (t1[i].t || t2[i].t) {
    Push_down(i, l, r);
  }
  int mid = l + r >> 1;
  if (tl <= mid) {
    Update(i << 1, l, mid, tl, tr, v);
  }
  if (tr > mid) {
    Update(i << 1 | 1, mid + 1, r, tl, tr, v);
  }
  Push_up(i);
}

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);
  cin >> n >> m;
  for (int i = 1; i <= n; ++i) {
    cin >> a[i];
  }
  Build(1, 1, n);
  while (m--) {
    cin >> op >> x >> y;
    if (op == 1) {
      cin >> z;
      Update(1, 1, n, x, y, z);
    } else if (op == 2) {
      cout << setprecision(4) << fixed << Query(t1, 1, 1, n, x, y) / (y - x + 1) << '\n';
    } else {
      cout << setprecision(4) << fixed << Query(t2, 1, 1, n, x, y) / (y - x + 1) - (Query(t1, 1, 1, n, x, y) / (y - x + 1) * Query(t1, 1, 1, n, x, y) / (y - x + 1)) << '\n';
    }
  }
  return 0;
}
2023/8/27 07:24
加载中...