https://www.acmicpc.net/problem/18619
18619번: Alakazam
The first line contains two integers n, q (1 ≤ n ≤ 250 000, 1 ≤ q ≤ 250 000) — the number of Alakazam in the line and the number of actions during the training. The following line contains n integers a1, a2, . . . , an (1 ≤ ai ≤ 106) — the
www.acmicpc.net
[알고리즘 분류]
Segment Tree with Lazy Propagation
레이지 세그 활용으로 매우 좋은 문제라고 생각한다.
구간을 섞어주면, 이 구간의 값들은 모두 해당하는 구간의 평균값으로 바뀌게 된다. 어떤 구간을 섞고, 이 구간을 일부만 포함하여 섞어도 이것이 성립하기 때문에, 레이지 세그를 열심히 구현하기만 하면 된다!
|
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
|
#include <bits/stdc++.h>
#define all(v) v.begin(),v.end()
using namespace std;
using ll = long long;
using ld = long double;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
typedef pair<int, ll> pil;
#define X first
#define Y second
#define endl '\n'
ld a[250250];
ld seg[1010101];
ld lazy[1010101];
int n;
ld init(int x, int s, int e) {
lazy[x] = -1;
if (s == e) {
return seg[x] = a[s];
}
int m = s + e >> 1;
return seg[x] = init(x * 2, s, m) + init(x * 2 + 1, m + 1, e);
}
void lazyProp(int x, int s, int e) {
if (lazy[x] >= -0.1) {
seg[x] = lazy[x] * (e - s + 1);
if (s != e) {
lazy[x * 2] = lazy[x];
lazy[x * 2 + 1] = lazy[x];
}
}
lazy[x] = -1;
}
void update(int x, int s, int e, int l, int r, ld k) {
lazyProp(x, s, e);
if (e < l || r < s) return;
if (l <= s && e <= r) {
lazy[x] = k;
lazyProp(x, s, e);
return;
}
int m = s + e >> 1;
update(x * 2, s, m, l, r, k);
update(x * 2 + 1, m + 1, e, l, r, k);
seg[x] = seg[x * 2] + seg[x * 2 + 1];
}
ld get(int x, int s, int e, int l, int r) {
lazyProp(x, s, e);
if (r < s || e < l) return (ld)0;
if (l <= s && e <= r) return seg[x];
int m = s + e >> 1;
return get(x * 2, s, m, l, r) + get(x * 2 + 1, m + 1, e, l, r);
}
void upd(int l, int r) {
ld g = get(1, 1, n, l, r) / (r - l + 1);
update(1, 1, n, l, r, g);
}
int main() {
ios::sync_with_stdio(false); cin.tie(nullptr);
int q; cin >> n >> q;
for (int i = 1; i <= n; i++) cin >> a[i];
for (int i = 0; i <= n*4; i++) lazy[i] = -1;
init(1, 1, n);
cout << fixed << setprecision(13);
for (int i = 0; i < q; i++) {
string op; int k; cin >> op >> k;
if (op == "get") {
cout << get(1, 1, n, k, k) << endl;
}
else {
int kk; cin >> kk;
upd(k, kk);
}
}
return 0;
}
|
cs |
'백준 문제풀이' 카테고리의 다른 글
| 2022 ICPC Seoul Regional Problem C. Empty Quadrilaterals (5) | 2022.11.21 |
|---|---|
| 백준 20306 - 블랙홀 (1) | 2022.11.12 |
| 백준 18032 - Dazzling Stars (0) | 2022.10.17 |
| 9/26 ~ 10/9 PS (0) | 2022.10.10 |
| 9/19 ~ 9/25 PS (0) | 2022.09.26 |