萌新求助线段树
  • 板块P1471 方差
  • 楼主QcpyWcpyQ
  • 当前回复0
  • 已保存回复0
  • 发布时间2022/9/13 22:15
  • 上次更新2023/10/27 11:41:36
查看原帖
萌新求助线段树
450861
QcpyWcpyQ楼主2022/9/13 22:15

3WA 7RE,跟着教练整的。

样例能过,但是会爆零

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 5;
int n, m, opt;
double a[N];

struct node {
  double sum, lazy;
} t1[N << 2], t2[N << 2];

inline int read() {
  int s = 0, f = 1;
  char ch = getchar();
  while (ch < '0' or ch > '9') {
    if (ch == '-')
      f = -1;
    ch = getchar();
  }
  while (ch >= '0' and ch <= '9') {
    s = (s << 1) + (s << 3) + (ch ^ 48);
    ch = getchar();
  }
  return f * s;
}

inline void write(int num) {
  if (num < 0)
    putchar('-'), num = -num;
  if (num > 9)
    write(num / 10);
  putchar(num % 10 + 48);
}

inline void pushup(int rt) {
  t1[rt].sum = t1[rt << 1].sum + t1[rt << 1 | 1].sum;
  t2[rt].sum = t2[rt << 1].sum + t2[rt << 1 | 1].sum;
}

inline void pushdown(int rt, int l, int r) {
  int mid = (l + r) >> 1;
  t2[rt << 1].lazy += t2[rt].lazy;
  t2[rt << 1].sum += t1[rt << 1].sum * (t2[rt].lazy * 2) + (mid - l + 1) * (t2[rt].lazy * t2[rt].lazy);
  t2[rt << 1 | 1].lazy += t2[rt].lazy;
  t2[rt << 1 | 1].sum += t1[rt << 1 | 1].sum * (t2[rt].lazy * 2) + (r - mid) * (t2[rt].lazy * t2[rt].lazy);
  t2[rt].lazy = 0;
  t1[rt << 1].lazy += t1[rt].lazy;
  t1[rt << 1].sum += (mid - l + 1) * t1[rt].lazy;
  t1[rt << 1 | 1].lazy += t1[rt].lazy;
  t1[rt << 1 | 1].sum += (r - mid) * t1[rt].lazy;
  t1[rt].lazy = 0;
}

inline void build(int rt, int l, int r) {
  if (l == r) {
    t1[rt].sum = a[l];
    t2[rt].sum = a[l] * a[l];
    return;
  }
  int mid = (l + r) >> 1;
  build(rt << 1, l, mid);
  build(rt << 1 | 1, mid + 1, r);
  pushup(rt);
}

inline double query(node tree[], int rt, int l, int r, int x, int y) {
  if (x <= l && r <= y)
    return tree[rt].sum;
  int mid = (l + r) >> 1;
  if (tree[rt].lazy)
    pushdown(rt, l, r);
  double ans = 0;
  if (x <= mid)
    ans = ans + query(tree, rt << 1, l, mid, x, y);
  if (y > mid)
    ans = ans + query(tree, rt << 1 | 1, mid + 1, r, x, y);
  pushup(rt);
  return ans;
}

inline void modify(int rt, int l, int r, int x, int y, double z) {
  if (x <= l && r <= y) {
    t2[rt].lazy += z;
    t2[rt].sum += t1[rt].sum * (z * 2) + (r - l + 1) * (z * z);
    t1[rt].lazy += z;
    t1[rt].sum += (r - l + 1) * z;
    return;
  }
  if (t1[rt].lazy || t2[rt].lazy)
    pushdown(rt, l, r);
  int mid = (l + r) >> 1;
  if (x <= mid)
    modify(rt << 1, l, mid, x, y, z);
  if (y > mid)
    modify(rt << 1 | 1, mid + 1, r, x, y, z);
  pushup(rt);
}

int main() {
  n = read(), m = read();
  for (int i = 1; i <= n; i++)
    a[i] = read();
  build(1, 1, n);
  while (m--) {
    opt = read();
    if (opt == 1) {
      int x, y;
      double z;
      x = read(), y = read();
      scanf("%lf", &z);
      modify(1, 1, n, x, y, z);
    }
    if (opt == 2) {
      int x, y;
      x = read(), y = read();
      printf("%.4lf\n", query(t1, 1, 1, n, x, y) / ((y - x + 1) * 1.0));
    }
    if (opt == 3) {
      int x, y;
      x = read(), y = read();
      printf("%.4lf\n", (query(t2, 1, 1, n, x, y) / ((y - x + 1) * 1.0)) -
                        (query(t1, 1, 1, n, x, y) / ((y - x + 1) * 1.0)) *
                        (query(t1, 1, 1, n, x, y) / ((y - x + 1) * 1.0)));
    }
  }
  return 0;
}

2022/9/13 22:15
加载中...