반응형

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

 

16978번: 수열과 쿼리 22

길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. 1 i v: Ai = v로 변경한다. 2 k i j: k번째 1번 쿼리까지 적용되었을 때, Ai, Ai+1, ..., Aj의 합을 출력한다.

www.acmicpc.net

 

 

[ 문제풀이 ]

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

https://rudalsd.tistory.com/364

 

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

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

rudalsd.tistory.com

 

1. arr배열에 수열을 입력받고, 비재귀세그먼트 트리를 이용하여 구간합을 구해줍니다.

 

2. cmd가 1인 쿼리와 2인 쿼리를 각각 저장하고, cmd가 2인 쿼리를 k를 기준으로 오름차순으로 정렬합니다.

 

3. 현재 상태에서 cmd가 1인 k번 쿼리까지 진행해 준 후, cmd가 2인 쿼리를 진행하고, 순서에 맞게 ans 배열에 저장합니다.

 

4. ans 배열을 출력합니다.

 

[ 소스코드 ]

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
#include<iostream>
#include<vector>
#include<algorithm>
#define ll long long
 
using namespace std;
 
struct query2 {
    int k, i, j;
    int seq;
};
 
struct cmp {
    bool operator()(query2 left, query2 right) {
        return left.k < right.k;
    }
};
 
int N, M;
ll segTree[200000];
vector<pair<int, int>> query;
vector<query2> queryArr;
ll ans[100000];
int arr[100001];
 
void updateTree(int idx, int n)
{
    while (idx) {
        segTree[idx] += n;
        idx >>= 1;
    }
}
 
ll getTree(int l, int r)
{
    ll ret = 0;
 
    while (l <= r) {
        if (l & 1) {
            ret += segTree[l];
            l++;
        }
        if (~r & 1) {
            ret += segTree[r];
            r--;
        }
        l >>= 1;
        r >>= 1;
    }
 
    return ret;
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> N;
 
    for (int i = 0; i < N; i++) {
        int n;
        cin >> n;
        arr[i] = n;
        updateTree(N + i, n);
    }
 
    cin >> M;
    int cnt = 0;
 
    for (int i = 0; i < M; i++) {
        int cmd;
        cin >> cmd;
 
        if (cmd == 1) {
            int i, v;
            cin >> i >> v;
            query.push_back({ i,v });
        }
        else {
            int k, i, j;
            cin >> k >> i >> j;
            queryArr.push_back({ k,i,j,cnt++ });
        }
    }
 
    sort(queryArr.begin(), queryArr.end(), cmp());
 
    int cur = 0;
 
    for (auto& next : queryArr) {
        int k = next.k;
        for (int i = cur; i < k; i++) {
            int a = query[i].first;
            int b = query[i].second;
            updateTree(a + N - 1, b - arr[a-1]);
            arr[a - 1] = b;
        }
        cur = k;
 
        ans[next.seq] = getTree(N + next.i - 1, N + next.j - 1);
    }
 
    for (int i = 0; i < cnt; i++) {
        cout << ans[i] << '\n';
    }
}
cs
반응형
저작자표시 비영리 변경금지

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

[ 백준 ] 14459번 - 소가 길을 건너간 이유 11 (C++)  (0) 2023.08.03
[ 백준 ] 15967번 - 에바쿰 (C++)  (0) 2023.08.02
[ 백준 ] 19940번 - 피자 오븐 (C++)  (0) 2023.07.31
[ 백준 ] 14852번 - 타일 채우기 3 (C++)  (0) 2023.07.30
[ 백준 ] 16954번 - 움직이는 미로 탈출 (C++)  (0) 2023.07.29

+ Recent posts

티스토리툴바