[P3] 백준 13544번 수열과 쿼리 3 C++ 세그먼트 트리, 머지소트 트리

리뷰

 

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

간만에 푼 머지소트 트리 문제, 예제 답이 제대로 나오지 않아 한참 찾았는데 query 함수 내에서 범위 처리를 잘못했었다.

세그먼트 트리 문제는 항상 조그만 실수에도 문제 전체가 달라져 버리니 주의 요망

 

 

전역 변수

• N : 수열의 최대 길이를 저장하기 위한 정수형 상수 변수
• n : 문제에 주어지는 수열의 크기
• m : 문제에 주어지는 쿼리의 개수
• i : 탐색할 범위의 왼쪽
• j : 탐색할 범위의 오른쪽
• k : 탐색할 값
• last : 이전 쿼리의 결과
• nodes : 수열 정보를 저장하기 위한 정수형 배열
• tree : 세그먼트 트리 정보를 저장하기 위한 정수형 벡터 배열

 

함수

1. build

void build(int node, int s, int e)

 

머지 소트 트리의 초기화를 위한 함수

1. 리프 노드 도달 시 수열의 각 인덱스를 단일 인자로 갖는 벡터로 저장해 준다.
2. 리프 노드가 아닐 경우 좌, 우 자식으로 재귀를 뻗어나간다.
3. 재귀를 빠져나왔을 경우 좌우 자식 노드를 각각 정수형 벡터 타입 L, R로 초기화 한다.
4. 현재 노드의 벡터 크기를 L의 크기와 R의 크기를 더한 값으로 resize해준다.
5. merge 메서드를 통해 자식 노드를 합치면서 정렬을 수행해 준다.

 

2. query

int query(int node, int s, int e, int L, int R, int val)

 

수열의 범위 내에서 val보다 큰 값의 개수를 찾는 함수

1. 범위를 벗어나면 0을 리턴해 준다.
2. 범위가 겹치면 upper_bound를 통해 현재 노드 벡터에서 val보다 큰 이터레이터를 찾아준다.
3. 현재 노드 벡터의 end에서 it을 뺀 값을 리턴해 주면 val보다 큰 값의 개수를 구할 수 있다.
4. 범위가 겹치지 않으면 마찬가지로 좌, 우 자식 노드를 재귀적으로 탐색해 준다.
5. 탐색이 완료된 값은 왼쪽 오른쪽 각각 정수형 변수 left, right로 저장해 준다.
6. left + right값을 리턴해 준다.

 

문제풀이

1. n값을 입력 받고, 수열의 1 ~ n번째 수를 nodes배열에 입력 받아준다.
2. build 함수를 통해 머지 소트 트리를 초기화 해준다.
3. m값을 입력 받고, m번의 반복문을 통해 쿼리 인자를 입력받아준다.
4. a, b, c를 입력 받고 각각을 last와 XOR 연산한 값을 i, j, k값으로 저장해 준다.
5. query 함수를 통해 i ~ j범위 내에서 k보다 큰 값의 개수를 찾아 last에 저장해 준다.
6. last를 줄 바꿈을 구분으로 출력해 주고 탐색을 이어 나간다.

 

참고 사항

아주 기본적인 머지 소트 트리에 XOR 연산을 끼얹은 문제다.

 

 

정답 코드

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

const int N = 100001;
int n, m, i, j, k, last;
int nodes[N];
vector<int> tree[N * 4];

void build(int node, int s, int e) {
	if (s == e) tree[node] = { nodes[s] };
	else {
		int mid = (s + e) / 2;
		build(node * 2, s, mid);
		build(node * 2 + 1, mid + 1, e);
		vector<int>& L = tree[node * 2];
		vector<int>& R = tree[node * 2 + 1];
		tree[node].resize(L.size() + R.size());
		merge(L.begin(), L.end(), R.begin(), R.end(), tree[node].begin());
	}
}

int query(int node, int s, int e, int L, int R, int val) {
	if (R < s || e < L) return 0;
	if (L <= s && e <= R) {
		auto it = upper_bound(tree[node].begin(), tree[node].end(), val);
		return tree[node].end() - it;
	}
	int mid = (s + e) / 2;
	int left = query(node * 2, s, mid, L, R, val);
	int right = query(node * 2 + 1, mid + 1, e, L, R, val);
	return left + right;
}

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

	cin >> n;
	for (int i = 1; i <= n; ++i) cin >> nodes[i];
	build(1, 1, n);
	
	cin >> m;
	while (m--) {
		int a, b, c;  cin >> a >> b >> c;
		i = last ^ a;
		j = last ^ b;
		k = last ^ c;
		last = query(1, 1, n, i, j, k);
		cout << last << "\n";
	}
}