https://www.acmicpc.net/problem/1275
문제
모두 알다시피 동호는 커피숍의 마담이다. (마담이 무엇인지는 본인에게 물어보도록 하자.)
어느 날 커피숍의 손님 A 씨가 동호에게 게임을 하자고 했다.
그 게임은 다음과 같은 규칙을 갖는다.
N개의 정수가 있으면, 동호는 다음과 같이 말한다. “3~7번째 수의 합은 무엇이죠?” 그러면 상대방은 “그 답은 000입니다. 그리고 8번째 수를 2로 고치도록 하죠” 그러면 동호는 “네 알겠습니다.”라고 한 뒤에 다시 상대방이 동호가 했던 것처럼 “8~9번째 수의 합은 무엇이죠?”라고 묻게 된다. 이 것을 번갈아 가면서 반복하는 게임이다.
당신은 이 게임의 심판 역을 맡았다. 요컨대, 질문에 대한 답들을 미리 알아야 한다는 것이다.
당신의 머리가 출중하다면 10만개 가량 되는 정수와 10만 턴 정도 되는 게임을 기억할 수 있을 것이다. 몇 판 이 게임을 즐기던 동호는 많은 사람들이 이 게임을 하기를 바라게 되었고, 당신에게 심판 프로그램을 구현해달라고 요청했다.
입력
첫째 줄에 수의 개수 N과 턴의 개수 Q가 주어진다.(1 ≤ N, Q ≤ 100,000) 둘째 줄에는 처음 배열에 들어가 있는 정수 N개가 주어진다. 세 번째 줄에서 Q+2번째 줄까지는 x y a b의 형식으로 x~y까지의 합을 구하여라, a번째 수를 b로 바꾸어라 라는 뜻의 데이터가 주어진다.
입력되는 모든 수는 -231보다 크거나 같고, 231-1보다 작거나 같은 정수이다.
출력
한 턴마다 구한 합을 한 줄마다 한 개씩 출력한다.
세그먼트 트리를 연습해볼겸 선정한 문제이다. 세그먼트 트리를 생성하고 그것을 통하여 구간합을 구하고 원소를 바꾸는 연습을 할 수 있다.
#include <iostream>
using namespace std;
int N, Q;
long long ans = 0;
long long arr[100001] = { 0 };
long long seg[400004] = { 0 };
long long init_seg(int s, int e, int node) {
if (s == e) {
return seg[node] = arr[s];
}
int mid = (s + e) / 2;
seg[node] = init_seg(s, mid, node * 2) + init_seg(mid + 1, e, node * 2 + 1);
return seg[node];
}
long long sum(int s, int e, int node, int left, int right) {
if (e < left || s > right) return 0;
else if (s >= left && e <= right) return seg[node];
int mid = (s + e) / 2;
return sum(s, mid, node * 2, left, right) + sum(mid + 1, e, node * 2 + 1, left, right);
}
void update(int s, int e, int node, int idx, long long dif) {
if (e < idx || s > idx) return;
seg[node] += dif;
if (s == e) return;
int mid = (s + e) / 2;
update(s, mid, node * 2, idx, dif);
update(mid + 1, e, node * 2 + 1, idx, dif);
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> N >> Q;
for (int i = 1; i <= N; i++) {
cin >> arr[i];
}
init_seg(1, N, 1);
for (int i = 1; i <= Q; i++) {
long long c, d;
cin >> c >> d;
cout << sum(1, N, 1, min(c, d), max(c, d)) << "\n";
cin >> c >> d;
update(1, N, 1, c, d - arr[c]);
arr[c] = d;
}
return 0;
}
update와 sum 함수 내에서 arr 배열은 사용하지 않고 seg 배열만 사용하고 seg [c]의 값 역시 바뀌니깐 arr [c] = d의 코드가 필요 없다고 생각했는데 정작 update의 인자로 arr [c]를 사용한다는 것을 간과하였다.
오늘 하루종일 SWEA 문제 백트래킹을 힘겹게 하고 또 이 문제도 쉽사리 되지 않아서 자신감이 떨어지는 하루였다. 내일은 새로운 마음가짐으로 기분 좋게 코딩을 해야 할 것이다!
'코딩 > 백준' 카테고리의 다른 글
[백준] 11437번 LCA - C/C++ (0) | 2022.01.27 |
---|---|
[백준] 10986번 나머지 합 - C/C++ (0) | 2022.01.26 |
[백준] 1091번 카드 섞기 - C/C++ (0) | 2022.01.24 |
[백준] 24041번 성싶당 밀키트 - C/C++ (2) | 2022.01.22 |
[백준] 24268번 2022는 무엇이 특별할까? - C/C++ (0) | 2022.01.21 |