P1471 方差

发表于 分类于 阅读次数： Waline： 本文字数： 670 阅读时长 ≈ 2 分钟

考点

  • 线段树

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 50;
int n, m;
double a[maxn];

// s1：普通和
// s2: 平方和
struct {
  int l, r;
  double s1, s2, tag;
#define l(x) tr[x].l
#define r(x) tr[x].r
#define s1(x) tr[x].s1
#define s2(x) tr[x].s2
#define tag(x) tr[x].tag
#define lc(x) x * 2
#define rc(x) x * 2 + 1
} tr[4 * maxn];

void up(int p) {
  s1(p) = s1(lc(p)) + s1(rc(p));
  s2(p) = s2(lc(p)) + s2(rc(p));
}

void build(int p, int l, int r) {
  l(p) = l, r(p) = r;
  if (l == r) {
    s1(p) = a[l], s2(p) = a[l] * a[l];
    return;
  }
  int mid = (l + r) / 2;
  build(lc(p), l, mid), build(rc(p), mid + 1, r);
  up(p);
}

void add(int p, double v) {
  s2(p) += (r(p) - l(p) + 1) * v * v + 2 * v * s1(p);
  s1(p) += (r(p) - l(p) + 1) * v;
}

void down(int p) {
  if (tag(p)) {
    add(lc(p), tag(p)), add(rc(p), tag(p));
    tag(lc(p)) += tag(p), tag(rc(p)) += tag(p);
    tag(p) = 0;
  }
}

void update(int p, int l, int r, double v) {
  if (l(p) >= l && r(p) <= r) {
    add(p, v);
    tag(p) += v;
    return;
  }
  down(p);
  int mid = (r(p) + l(p)) / 2;
  if (l <= mid) update(lc(p), l, r, v);
  if (r > mid) update(rc(p), l, r, v);
  up(p);
}

double ask(int p, int l, int r, int opt) {
  if (l <= l(p) && r(p) <= r) {
    if (opt == 1) return s1(p);
    if (opt == 2) return s2(p);
  }
  down(p);
  int mid = (l(p) + r(p)) / 2;
  double s = 0;
  if (l <= mid) s += ask(lc(p), l, r, opt);
  if (r > mid) s += ask(rc(p), l, r, opt);
  return s;
}

int main() {
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; ++i) scanf("%lf", &a[i]);
  build(1, 1, n);
  int opt, x, y, len;
  double k, s1, s2, av, t;
  while (m--) {
    scanf("%d%d%d", &opt, &x, &y);
    len = (y - x + 1);
    if (opt == 1) {
      scanf("%lf", &k);
      update(1, x, y, k);
    } else if (opt == 2) {
      t = ask(1, x, y, 1) / len;
      printf("%.4lf\n", t);
    } else {
      s1 = ask(1, x, y, 1), s2 = ask(1, x, y, 2);
      av = s1 / len;
      t = (s2 - 2 * av * s1 + len * av * av) / len;
      printf("%.4lf\n", t);
    }
  }
  return 0;
}

思路

一道数学题。

假设有{x1, x2, x3, x4}序列，

长度为n，区间和等于x1 + x2 + x3 + x4 = s1，均值等于s1 / n = y，那么方差等于： \[ \frac{\left( x_1-y \right) ^2+\left( x_2-y \right) ^2+\left( x_3-y \right) ^2+\left( x_4-y \right) ^2}{n} \] 只看分子，展开得到 \[ \left( {x_1}^2-2x_1y+y^2 \right) +\left( {x_2}^2-2x_2y+y^2 \right) +\left( {x_3}^2-2x_3y+y^2 \right) +\left( {x_4}^2-2x_4y+y^2 \right) \] 整理一下得到 \[ \left( {x_1}^2+{x_2}^2+{x_3}^2+{x_4}^2 \right) +ny^2-2y\left( x_1+x_2+x_3+x_4 \right) \] 设区间平方和为s2，那么上述式子可以简化为 \[ s_2-2ys_1+ny^2 \] 所以线段树维护区间和s1和区间平方和s2即可

假设现在，每个单位都要新增k，设当前某个位置的原值为x \[ \text{之前的平方值：}x^2 \]

\[ \text{现在的平方值：}\left( x+k \right) ^2=x^2+2xk+k^2 \]

那么对于整个区间而言，区间平方和增长了： \[ nk^2+2ks_1 \]