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

🔗 문제 링크

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

✍️ 문제 풀이

해당 문제는 수열의 특정 구간 내의 짝수 개수와 홀수 개수를 구하는 문제로, 세그먼트 트리 알고리즘을 사용하여 풀이했다.

1) 수열을 저장할 datas, pair(짝수 개수, 홀수 개수) 트리를 저장할 tree 배열을 선언한다. 이 때 트리의 크기는 수열 배열의 최대 크기의 4배 이상으로 설정한다.

2) 수의 개수 n을 입력받아 저장하고, n개의 수를 입력받아 datas에 저장한다. 이후 쿼리의 개수 m을 입력 받아 저장한다.

3) init() 함수를 통해 pair(짝수 개수, 홀수 개수) 트리를 초기화 한다.

• 최상위 노드부터 시작해 데이터 범위를 반씩 분할하여 구간곱을 저장하는 방식으로 트리를 채운다. 재귀를 통해 가장 작은 범위의 값을 구해, 그 값들로 더 큰 범위의 값을 구한다.
  • 현재 순서 노드의 값 = pair(왼쪽 자식 노드의 짝수 개수 + 오른쪽 자식 노드의 짝수 개수, 왼쪽 자식 노드의 홀수 개수 + 오른쪽 자식 노드의 홀수 개수)
• 더 이상 분할할 수 없을 때(범위 내에 수가 하나 뿐일 때)
  • 해당 수가 짝수라면 pair(1, 0)를 현재 노드의 값으로 초기화
  • 해당 수가 홀수라면 pari(0, 1)를 현재 노드의 값으로 초기화

4) m번의 쿼리를 실행한다.

• 쿼리로 주어지는 수 a, b, c를 입력 받는다.
• a가 1이라면 update()를 실행하고, b번째 수를 c로 변경한다.
  • update()는 하위 노드 값부터 상위 노드로 바뀌는 방식으로 진행한다.
    • 범위 밖에 있는 경우 무시한다.
    • 범위 안에 있다면
      • 더 이상 분할할 수 없을 때(범위 내에 수가 하나 뿐일 때)
        • 변경할 수가 짝수라면 현재 순서 노드를 pair(1, 0)으로 변경한다.
        • 변경할 수가 홀수라면 현재 순서 노드를 pair(0, 1)으로 변경한다.
      • 분할할 수 있다면 데이터 범위를 반으로 분할해
        현재 순서 노드의 값 = pair(왼쪽 자식 노드의 짝수 개수 + 오른쪽 자식 노드의 짝수 개수, 왼쪽 자식 노드의 홀수 개수 + 오른쪽 자식 노드의 홀수 개수)로 변경한다.
  • update() 함수 실행 이후 datas의 특정 인덱스 값도 변경해주어야 한다.
• a가 2라면 b, c 범위 내 짝수 개수를 출력한다.
• a가 3이라면 b, c 범위 내 홀수 개수를 출력한다.
  • get() 함수를 통해 현재 순서에서 구해야하는 범위의 짝수 개수 및 홀수 개수를 구한다.
    • 범위 밖에 있는 경우 pair(0, 0)을 반환한다.
    • 범위 안에 있는 경우 현재 순서 노드의 값을 반환한다.
    • 범위에 걸쳐 있는 경우 현재 범위의 절반으로 나누어 각 범위에 대해 get()을 실행한다.
  • 짝수 개수는 get().first를, 홀수 개수는 second를 출력하면 된다.

🖥️ 풀이 코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef pair<long long, int> pii;	// 짝수, 홀수 개수

pii tree[400004];
int datas[100001];
int n, m;

pii init(int start, int end, int node)
{
	if (start == end)
	{
		if (datas[start] % 2 == 0)
			return tree[node] = pii(1, 0);
		else
			return tree[node] = pii(0, 1);
	}
	int mid = start + (end - start) / 2;
	pii leftNode = init(start, mid, node * 2);
	pii rightNode = init(mid + 1, end, node * 2 + 1);
	return tree[node] = pii(leftNode.first + rightNode.first,
		leftNode.second + rightNode.second);
}

pii get(int start, int end, int node, int left, int right)
{
	if (end < left || right < start) return pii(0, 0);
	if (left <= start && end <= right)
		return tree[node];
	int mid = start + (end - start) / 2;
	pii leftNode = get(start, mid, node * 2, left, right);
	pii rightNode = get(mid + 1, end, node * 2 + 1, left, right);
	return pii(leftNode.first + rightNode.first, leftNode.second + rightNode.second);
}

pii update(int start, int end, int node, int index, int dif)
{
	if (index < start || end < index) return tree[node];
	if (start == end)
	{
		if (dif % 2 == 0)
			return tree[node] = pii(1, 0);
		else
			return tree[node] = pii(0, 1);
	}
	int mid = start + (end - start) / 2;
	pii leftNode = update(start, mid, node * 2, index, dif);
	pii rightNode = update(mid + 1, end, node * 2 + 1, index, dif);
	return tree[node] = pii(leftNode.first + rightNode.first, leftNode.second + rightNode.second);
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr); cout.tie(nullptr);

	cin >> n;
	for (int i = 1; i <= n; i++)
		cin >> datas[i];
	init(1, n, 1);
	cin >> m;
	for (int i = 0; i < m; i++)
	{
		int a, b, c;
		cin >> a >> b >> c;
		if (a == 1)
		{
			update(1, n, 1, b, c);
			datas[b] = c;
		}
		else if (a == 2)
			cout << get(1, n, 1, b, c).first << '\n';
		else
			cout << get(1, n, 1, b, c).second << '\n';
	}
}