[ BOJ] 18436 수열과 쿼리 37

 

 

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

18436번: 수열과 쿼리 37

알고리즘: Segment tree

 

시간복잡도: $O((N+M)logN)$

---

접근:

1. 구간 쿼리 및 쿼리 개수 $(M\le 10^5)$

 

정해진 구간 내의 짝수 및 홀수의 개수를 구하는 문제이다.

 

$A_i$가 홀수이면 1, 짝수이면 0으로 segment tree의 리프 노드에 저장해두고,

부모 노드는 자식 노드들의 합으로 표현해주면 구간 내 홀수의 개수를 구해줄 수 있다.

(짝수의 개수는 (r-l+1)-홀수 개수로 구해줄 수 있다.)

 

만약 $A_i$의 값이 홀수에서 짝수로 변경되었다면,

해당 리프 노드부터 root까지 탐색하면서 값을 1씩 빼주면서 트리를 갱신할 수 있다.

 

 

	// 18436: 수열과 쿼리 37
	#include<iostream>
	using namespace std;
	int N, M, a[100001], q, u, v, tree_size = 1;
	int tree[1<<18];
	void updateST(int idx, int val) // count odd
	{
	int t;
	if ( (a[idx] & 1)^(val & 1) )
	{
	t = (val & 1)?1:-1;
	a[idx] = val; // update a[] when state(even,odd) is changed
	idx += tree_size;
	while (idx >= 1)
	{
	tree[idx] += t;
	idx >>= 1;
	}
	}
	}
	int cnt_odd(int l, int r)
	{
	int cnt = 0;
	l += tree_size, r += tree_size;
	while (l <= r)
	{
	if (l & 1) cnt += tree[l++];
	if (~r & 1) cnt += tree[r--];
	l >>= 1, r >>= 1;
	}
	return cnt;
	}
	int main()
	{
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin >> N;
	while (tree_size < N) tree_size <<= 1;
	for (int i = 0; i < N; ++i)
	{
	cin >> u;
	updateST(i, u);
	}
	cin >> M;
	for (int i = 0; i < M; ++i)
	{
	cin >> q >> u >> v;
	if (q == 1) updateST(u-1, v);
	else if (q == 2) cout << (v-u+1)-cnt_odd(u-1, v-1) << "\n";
	else cout << cnt_odd(u-1, v-1) << "\n";
	}
	return 0;
	}

view raw BOJ_18436.cpp hosted with ❤ by GitHub