취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 17400번 문제인 깃발춤이다.
문제는 아래 링크를 확인하자.

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

이 문제에서는 정수배열과 두 가지 쿼리가 주어진다. 하나는 주어지는 구간에서 홀수번째 수의 합과 짝수번째 수의 합의 차의 절댓값을 구하는 쿼리이고, 다른 하나는 정수배열의 값 하나를 업데이트하는 쿼리이다.

항상 홀수번째 수와 짝수번째 수의 차만을 구할 것이므로, 홀수번째 수들을 부호를 반대로 저장하는 세그먼트트리를 이용하면 구간합을 구해 절댓값을 계산하는 것으로 어떤 구간이 주어지더라도 그 구간의 홀수번째 수의 합과 짝수번째 수의 합의 차의 절댓값을 구할 수 있게 된다. 

업데이트 시에도 홀수번째 숫자의 변화량의 부호를 반대로 넣어주자.

32비트 정수범위를 넘는 수를 다루는 경우가 생길 수 있다는 점에 유의하자.

아래는 제출한 소스코드이다.

#include <iostream>
using namespace std;
typedef long long ll;

ll arr[300001];
ll seg[1048577];

ll init(int L, int R, int sI) {
	if (L == R) return seg[sI] = arr[L];
	return seg[sI] = init(L, (L + R) / 2, sI * 2) + init((L + R) / 2 + 1, R, sI * 2 + 1);
}

void update(int L, int R, int qI, int qVal) {
	int sI = 1;
	while (L < R) {
		seg[sI] += qVal;
		int mid = (L + R) / 2;
		if (qI > mid) L = mid + 1, sI = sI * 2 + 1;
		else R = mid, sI = sI * 2;
	}

	seg[sI] += qVal;
}

ll rangesum(int L, int R, int qL, int qR, int sI) {
	if (R < qL || qR < L) return 0;
	if (qL <= L && R <= qR) return seg[sI];
	return rangesum(L, (L + R) / 2, qL, qR, sI * 2) + rangesum((L + R) / 2 + 1, R, qL, qR, sI * 2 + 1);
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	int N, Q; cin >> N >> Q;
	for (int i = 1; i <= N; i++) {
		ll& x = arr[i]; cin >> x;
		if (i & 1) x *= -1;
	}

	init(1, N, 1);

	while (Q--) {
		int x; cin >> x;
		if (x == 1) {
			int L, R; cin >> L >> R;
			cout << abs(rangesum(1, N, L, R, 1)) << '\n';
		}
		else {
			int qI, qVal; cin >> qI >> qVal;
			if (qI & 1) update(1, N, qI, -qVal);
			else update(1, N, qI, qVal);
		}
	}
}