[BOJ | 백준] 18436번: 수열과 쿼리 37

by Kimcoding on 2020-02-28 19:33

in BOJ

문제 설명

BOJ 18436

하나의 원소를 업데이트하고 구간의 홀수, 짝수의 개수를 구하는 쿼리를 구현하는 문제입니다.

풀이

업데이트와 구간 쿼리를 해야 하는데

N이 최대 10만, M이 최대 10만이라 세그먼트 트리를 사용해야 합니다.

구간합을 구하는 기본 세그먼트 트리 문제입니다.

구간합을 저장하는 배열을 홀수, 짝수로 나누어 odd, even이라고 선언하겠습니다.

update를 할 때 변경하려는 값이 홀수이면 odd = 1, even = 0 짝수이면 even = 1, odd = 0을 갱신해 주면 됩니다.

그렇게 하면 홀수의 구간합과 짝수의 구간합을 구할 수 있고

구간합이 개수와 동일하므로

쿼리를 할 때 홀수, 짝수의 개수를 구할 수 있습니다.

기본 세그먼트 트리 문제라 세그먼트 트리를 공부하고 바로 풀어봐도 좋은 문제 같아요!

소스 코드

#include <bits/stdc++.h>
#define FIO ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define FOR(i,a,b) for(int i=a;i<=b;i++)
using namespace std;

struct ST {
	int* odd, *even, leaf;
	ST(int n) {
		leaf = (1 << (int)ceil(log2(n)));
		odd = new int[leaf * 2]();
		even = new int[leaf * 2]();
		leaf--;
	}
	void update(int idx, int val) {
		idx += leaf;
		if (val & 1) odd[idx] = 1, even[idx] = 0;
		else odd[idx] = 0, even[idx] = 1;
		while (idx >>= 1) {
			odd[idx] = odd[idx << 1] + odd[idx << 1 | 1];
			even[idx] = even[idx << 1] + even[idx << 1 | 1];
		}
	}
	int query(int l, int r, int c) {
		int ret = 0;
		l += leaf, r += leaf;
		for (; l <= r; l >>= 1, r >>= 1) {
			if (l & 1) ret += c ? odd[l++] : even[l++];
			if (~r & 1) ret += c ? odd[r--] : even[r--];
		}
		if (l == r) ret += c ? odd[l] : even[l];
		return ret;
	}
	~ST() {
		delete[] odd, delete[] even;
	}
};


int main() {
	FIO;
	int n; cin >> n;
	ST st(n);
	FOR(i, 1, n) {
		int x; cin >> x;
		st.update(i, x);
	}
	int m; cin >> m;
	while (m--) {
		int a, b, c; cin >> a >> b >> c;
		if (a == 1) st.update(b, c);
		else cout << st.query(b, c, a - 2) << '\n';
	}
	return 0;
}