반응형

https://www.acmicpc.net/problem/14419

 

14419번: Foehn Phenomena

Initially, the altitudes of the Spot 0, 1, 2, 3 are 0, 4, 1, 8, respectively. After the tectonic movement on the first day, the altitudes become 0, 6, 3, 8, respectively. At that moment, the temperatures of the wind are 0, -6, 0, -5, respectively.

www.acmicpc.net

 

 

[ 문제풀이 ]

이 문제를 풀기 전에 다음 글을 먼저 읽고 오시는 것을 추천드립니다.

https://rudalsd.tistory.com/364

 

[ 자료구조 ] 비재귀 세그먼트 트리 (Segment Tree)

1. 비재귀 세그먼트 트리 (Segment Tree) 재귀 세그먼트 트리에서는 항상 루트노드부터 시작했었습니다. 하지만 비재귀 세그먼트 트리에서는 반대로 리프노드부터 시작합니다. 2. 비재귀 세그먼트

rudalsd.tistory.com

 

1. arr 배열에 각 언덕의 높이를 저장하고, diff 배열에 arr[ i ] - arr[ i + 1 ]의 값을 저장합니다.

 

2. L, R, X가 입력되면 diff[ L - 1 ]의 값에 X를 빼주고, R != N일 때 diff[ R ]의 값에 X를 더해줍니다.

 

3. 해당 값을 기준으로 segmentTree를 업데이트해주고, segTree[ 1 ]의 값을 출력해 줍니다.

 

[ 소스코드 ]

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
#include<iostream>
#define ll long long
 
using namespace std;
 
int N, Q, S, T;
ll arr[200001];
ll diff[200000];
ll segTree[400000];
 
void updateTree(int i)
{
    if (diff[i] < 0) {
        segTree[i + N] = diff[i] * S;
    }
    else {
        segTree[i + N] = diff[i] * T;
    }
 
    int temp = i + N;
    temp >>= 1;
    while (temp != 0) {
        segTree[temp] = segTree[temp << 1] + segTree[temp << 1 | 1];
        temp >>= 1;
    }
}
 
int main()
{
    scanf("%d %d %d %d", &N, &Q, &S, &T);
 
    for (int i = 0; i <= N; i++) {
        scanf("%lld", &arr[i]);
    }
 
    for (int i = 0; i < N; i++) {
        diff[i] = arr[i] - arr[i + 1];
    }
 
    for (int i = 0; i < N; i++) {
        if (arr[i] < arr[i + 1]) {
            segTree[i + N] = (arr[i] - arr[i + 1]) * S;
        }
        else {
            segTree[i + N] = (arr[i] - arr[i + 1]) * T;
        }
    }
 
    for (int i = N - 1; i >= 1; i--) {
        segTree[i] = segTree[i << 1] + segTree[i << 1 | 1];
    }
 
    for (int i = 0; i < Q; i++) {
        int L, R;
        ll X;
        scanf("%d %d %lld", &L, &R, &X);
 
        diff[L - 1] -= X;
        if(R != N) diff[R] += X;
 
        updateTree(L - 1);
        if (R != N) updateTree(R);
        printf("%lld\n", segTree[1]);
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

'백준' 카테고리의 다른 글

[ 백준 ] 14268번 - 회사 문화 2 (C++)  (0) 2023.05.09
[ 백준 ] 14267번 - 회사 문화 1 (C++)  (0) 2023.05.08
[ 백준 ] 12844번 - XOR (C++)  (0) 2023.05.06
[ 백준 ] 11003번 - 최솟값 찾기 (C++)  (0) 2023.05.05
[ 백준 ] 1395번 - 스위치 (C++)  (0) 2023.05.03

+ Recent posts

티스토리툴바