[백준] 커피숍2

문제

모두 알다시피 동호는 커피숍의 마담이다. (마담이 무엇인지는 본인에게 물어보도록 하자.)

어느 날 커피숍의 손님 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로 바꾸어라 라는 뜻의 데이터가 주어진다.

입력되는 모든 수는 32비트 부호있는 정수이다.

출력

한 턴마다 구한 합을 한 줄마다 한 개씩 출력한다.

예제 입력 1 복사

5 2 1 2 3 4 5 2 3 3 1 3 5 4 1

예제 출력 1 복사

5 10

---

오랜만에 풀어본 세그먼트 트리 문제이다.

내 블로그의 기본 알고리즘 파트에 세그먼트 트리를 정리해놨으니 참고하면 좋다.

사실 이 문제는 기본 세그먼트 트리에서 딱히 변형된 게 없어 몇가지를 제외하면 기본 코드를 그대로 쓰면 된다.

 

주의할 점은 문제에서 나오듯이 x가 y보다 큰 경우 swap을 해줘야 한다는 것과,

입력값이 int 범위로 들어오지만 이 값들이 합해질 경우 int 범위를 넘을 수 있으므로 범위값을 구하는 range 벡터에 long long 형으로 선언해야 한다는 것이다.

 

이를 제외하면 기본 세그먼트 트리와 똑같은 문제이다.

 

 

코드 원본 : 

https://github.com/chosh95/STUDY/blob/master/BaekJoon/2020/%EC%BB%A4%ED%94%BC%EC%88%8D2%20(1275%EB%B2%88).cpp

chosh95/STUDY

 

C++ 코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>
using namespace std;
typedef long long ll;
int p[100001];
vector<ll> range;
int N, Q;

ll init(int left, int right, int node) {
	if (left == right) return range[node] = p[left];
	int mid = (left + right) / 2;
	return range[node] = init(left, mid, node * 2) + init(mid + 1, right, node * 2 + 1);
}

//left, right는 구하고자 하는 범위, nodeLeft, nodeRight는 현재 조사하는 범위, node는 현재 위치
ll query(int left, int right, int node, int nodeLeft, int nodeRight) {
	if (nodeRight < left || right < nodeLeft) return 0;
	if (left <= nodeLeft && nodeRight <= right) return range[node];
	int mid = (nodeLeft + nodeRight) / 2;
	return query(left, right, node * 2, nodeLeft, mid) + query(left, right, node * 2 + 1, mid + 1, nodeRight);
	
}

void update(int idx, int value, int node, int nodeLeft, int nodeRight) {
	if (idx < nodeLeft || nodeRight < idx) return;
	if (nodeLeft == nodeRight) {
		range[node] = value;
		return;
	}
	int mid = (nodeLeft + nodeRight) / 2;
	update(idx, value, node * 2, nodeLeft, mid);
	update(idx, value, node * 2 + 1, mid + 1, nodeRight);
	range[node] = range[node * 2] + range[node * 2 + 1];
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int x, y, a, b;
	cin >> N >> Q;
	range.resize(N * 4);
	for (int i = 0; i < N; i++) 
		cin >> p[i];

	init(0,N-1,1);

	for (int i = 0; i < Q; i++) {
		cin >> x >> y >> a >> b;
		if (x > y) swap(x, y);
		cout << query(x-1, y-1, 1, 0, N-1)<<"\n";
		update(a-1, b, 1, 0, N-1);
	}
}