Luogu P3707 [SDOI2017]相关分析

[模板] 线段树4(bushi

颓柿子啦

$a = \frac{\sum(x_i - \overline{x})(y_i - \overline{y})}{\sum(x_i - \overline{x})^2} = \frac{\sum x_i y_i - \sum \overline{x}y_i - \sum x_i \overline{y}+\sum \overline{x} \overline{y}}{\sum x_i^2 - \sum 2x_i\overline{x} + \sum\overline{x}^2}$.

将$\overline{x},\overline{y}$代入得:

$a = \frac{(R - L + 1)\sum x_iy_i - \sum x_i \sum y_i}{(R - L + 1)\sum x_i^2 - (\sum x_i)^2}$.

设 $s_0 = \sum x_i, s_1 = \sum y_i, s_2 = \sum x_i^2, s_3 = \sum x_iy_i$,答案为 $\frac{(R - L + 1)s_3 - s_0s_1}{(R - L + 1)s_2 - s_0^2}$.

区间求和,可以用线段树维护。

对于增加操作:

$s_0 = \sum (x_i + S) = \sum x_i + (R - L + 1)S$.

$s_1 = \sum (y_i + T) = \sum y_i + (R - L + 1)T$.

$s_2 = \sum (x_i + S) ^ 2 = \sum x_i^2 + 2S \sum x_i + (R - L + 1)S^2$.

$s_3 = \sum (x_i + S)(y_i + T) = \sum x_iy_i + T\sum x_i + S\sum y_i + (R - L + 1)ST.$

对于修改操作:

$s_0 = \sum(i + S) = \sum i + (R - L + 1)S$.

$s_1 = \sum(i + T) = \sum i + (R - L + 1)T$.

$s_2 = \sum(i + S)^2 = \sum i^2 + \sum S^2 + \sum 2Si = \sum i^2 + 2S\sum i + (R - L + 1) S^2$.

$s_3 = \sum(S+i)(T+i) = \sum ST + \sum (S+T) i + \sum i^2 = \sum i^2 + (S + T)\sum i + (R - L + 1)ST$.

$\sum i = \frac{i (i + 1)}{2}. \sum i^2 = \frac{i(i + 1)(2i + 1)}{6}.$写成函数.

非常的好写,非常的OC(棒读

用 long long 会被卡精度,必须能开double的都开double,强烈谴责。

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
100
101
102
103
104
105
106
107
108
109
#include <bits/stdc++.h>

typedef long long LL;
typedef double DB;
const int N = 2e5 + 233;
int n, m;
DB t[N << 2][4], x[N], y[N];
std::pair<DB, DB> tag[N << 2][2];

inline DB sumI(DB l, DB r) { return (l + r) * (r - l + 1) / 2; }
inline DB sumII(DB l, DB r) { return r * (r + 1) * (2 * r + 1) / 6 - l * (l - 1) * (2 * l - 1) / 6; }
inline void pushup(int p) { for (int i = 0; i <= 3; ++i) t[p][i] = t[p << 1][i] + t[p << 1 | 1][i]; }


void add(int p, int l, int r, DB S, DB T) {
t[p][2] += 2 * S * t[p][0] + (r - l + 1) * S * S;
t[p][3] += T * t[p][0] + S * t[p][1] + (r - l + 1) * S * T;
t[p][0] += (r - l + 1) * S, t[p][1] += (r - l + 1) * T;
tag[p][0].first += S, tag[p][0].second += T;
}

void set(int p, int l, int r, DB S, DB T) {
t[p][0] = sumI(l, r) + (r - l + 1) * S;
t[p][1] = sumI(l, r) + (r - l + 1) * T;
t[p][2] = (r - l + 1) * S * S + 2 * S * sumI(l, r) + sumII(l, r);
t[p][3] = (r - l + 1) * S * T + (S + T) * sumI(l, r) + sumII(l, r);
tag[p][0] = {0, 0}, tag[p][1] = {S, T};
}

inline void pushdown(int p, int l, int r) {
if (!tag[p][0].first && !tag[p][0].second && !tag[p][1].first && !tag[p][1].second) return;
int mid = (l + r) >> 1;
if (tag[p][1].first || tag[p][1].second) {
set(p << 1, l, mid, tag[p][1].first, tag[p][1].second);
set(p << 1 | 1, mid + 1, r, tag[p][1].first, tag[p][1].second);
}
if (tag[p][0].first || tag[p][0].second) {
add(p << 1, l, mid, tag[p][0].first, tag[p][0].second);
add(p << 1 | 1, mid + 1, r, tag[p][0].first, tag[p][0].second);
}
tag[p][1] = tag[p][0] = {0, 0};
}

void build(int p, int l, int r) {
if (l == r) {
t[p][0] = x[l], t[p][1] = y[l];
t[p][2] = x[l] * x[l], t[p][3] = x[l] * y[l];
return;
}
int mid = (l + r) >> 1;
build(p << 1, l, mid), build(p << 1 | 1, mid + 1, r);
pushup(p);
}

void modify(int p, int l, int r, int pl, int pr, DB S, DB T) {
if (l >= pl && r <= pr) return add(p, l, r, S, T);
int mid = (l + r) >> 1;
pushdown(p, l, r);
if (pl <= mid) modify(p << 1, l, mid, pl, pr, S, T);
if (pr > mid) modify(p << 1 | 1, mid + 1, r, pl, pr, S, T);
pushup(p);
}

void change(int p, int l, int r, int pl, int pr, DB S, DB T) {
if (l >= pl && r <= pr) return set(p, l, r, S, T);
int mid = (l + r) >> 1;
pushdown(p, l, r);
if (pl <= mid) change(p << 1, l, mid, pl, pr, S, T);
if (pr > mid) change(p << 1 | 1, mid + 1, r, pl, pr, S, T);
pushup(p);
}

DB query(int p, int l, int r, int pl, int pr, int id) {
if (l >= pl && r <= pr) return t[p][id];
int mid = (l + r) >> 1;
pushdown(p, l, r);
DB sum = 0;
if (pl <= mid) sum += query(p << 1, l, mid, pl, pr, id);
if (pr > mid) sum += query(p << 1 | 1, mid + 1, r, pl, pr, id);
return sum;
}

DB calc(int l, int r) {
DB s[4];
for (int i = 0; i <= 3; ++i) s[i] = query(1, 1, n, l, r, i);
return 1.0 * ((r - l + 1) * s[3] - s[0] * s[1]) / ((r - l + 1) * s[2] - s[0] * s[0]);
}

signed main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; ++i) scanf("%lf", x + i);
for (int i = 1; i <= n; ++i) scanf("%lf", y + i);
build(1, 1, n);
for (int i = 1; i <= m; ++i) {
int op;
DB l, r, s, t;
scanf("%d%lf%lf", &op, &l, &r);
if (op == 1) {
printf("%.10lf\n", calc(l, r));
} else if (op == 2) {
scanf("%lf%lf", &s, &t);
modify(1, 1, n, l, r, s, t);
} else {
scanf("%lf%lf", &s, &t);
change(1, 1, n, l, r, s, t);
}
}
return 0;
}

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×