[P4] 백준 17408번 수열과 쿼리 24 C++ 세그먼트 트리

리뷰

 

세그먼트 트리를 통해 수열의 특정 구간의 첫번째 최대값과 두번째 최대값을 구하고 그 합을 구해 출력하는 문제

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

 

문제 풀이

전역 변수

MAX_N : 노드의 최대 개수 10만을 상수형 정수타입으로 설정해 준다.

nodes : 수열의 정보를 담을 배열, 크기는 MAX_N으로 설정한다.

tree : 최대값과 인덱스를 담을 정수형 pair 배열, 크기는 MAX_N * 4로 설정한다.

n, m : 노드의 개수 및 쿼리의 개수 정보를 담을 변수

 

함수

1. 최대값을 갖는 세그먼트 트리를 만드는 함수

void build(int node, int start, int end)

 

1. 리프 노드 도달 시 배열의 값과 인덱스를 저장해 준다.
2. 이후 탐색을 통해 위로 올려주며 각 자식노드의 최대값을 상위 노드의 최대값과 인덱스로 갱신시켜 준다.

 

2. 구간의 최대값을 업데이트 해주는 함수

void update(int node, int start, int end, int idx, int val)

 

1. 리프 노드 도달 시 val과 idx를 업데이트 해준다.
2. 이후 탐색을 통해 위로 올려주며 각 자식노드의 최대값을 상위 노드의 최대값과 인덱스로 갱신시켜 준다.

3. 구간의 최대값과 인덱스를 구하는 함수

pair<int, int> query(int node, int start, int end, int L, int R)

 

1. L과 R 둘중 하나라도 start와 end의 범위를 벗어난 경우 문제 내 최소값인0과 범위를 벗어난 임의의 인덱스 출력
2. 구간 내의 경우 tree의 node번째 데이터를 리턴해 준다.
3. 더 구할 범위의 경우 이분 탐색과 재귀를 통해 left, right 정보를 받아온다.
4. left와 right의 값 비교를 통해 더 큰값을 리턴해 준다.

문제풀이

1. n값을 입력 받고, nodes 배열에 수열의 정보를 입력 받아준다.
2. build 함수를 통해 nodes 배열을 사용하여 세그먼트 트리를 만들어 준다.
3. m값을 입력 받고 m개의 쿼리를 실행해 준다, a, b, c를 통해 각 수를 입력받는다.
4. a가 1일 경우 update 함수를 통해 b - 1, c - 1구간을 업데이트 해준다. (0 based-index 형식이므로 1을 빼준 것)
5. b가 1일 경우 query 함수를 통해 b - 1, c - 1구간 중 최대값과 인덱스를 받아온다.
6. 업데이트 함수를 통해 해당 인덱스의 값을 0으로 업데이트 해준다.
7. 해당 구간의 최대값을 하나 더 뽑아온다.
8. 업데이트를 통해 이전에 6번에서 0으로 업데이트한 인덱스를 5에서 뽑아온 최대값으로 다시 업데이트 한다.
9. 두 최대값의 합을 출력해 준다.

 

참고 사항

2번 명령이 주어졌을 경우 O(4 * LogN) 크기로 시간상 괜찮아 보여 돌렸더니 꽤 빠른 속도로 동작 했다.

기존엔 벡터를 사용 했었는데 배열을 사용하니 더 빠른 속도로 동작이 가능한 것 같다.

 

 

정답 코드

#include<iostream>

using namespace std;

const int MAX_N = 100000;
int nodes[MAX_N];
pair<int, int> tree[MAX_N * 4];
int n, m;

void build(int node, int start, int end) {
	if (start == end) tree[node] = { nodes[start], start };
	else {
		int mid = (start + end) / 2;
		build(node * 2, start, mid);
		build(node * 2 + 1, mid + 1, end);
		if (tree[node * 2].first >= tree[node * 2 + 1].first) tree[node] = tree[node * 2];
		else tree[node] = tree[node * 2 + 1];
	}
}

void update(int node, int start, int end, int idx, int val) {
	if (start == end) tree[node] = { val, idx };
	else {
		int mid = (start + end) / 2;
		if (start <= idx && idx <= mid) update(node * 2, start, mid, idx, val);
		else update(node * 2 + 1, mid + 1, end, idx, val);
		if (tree[node * 2].first >= tree[node * 2 + 1].first) tree[node] = tree[node * 2];
		else tree[node] = tree[node * 2 + 1];
	}
}

pair<int, int> query(int node, int start, int end, int L, int R) {
	if (R < start || end < L) return { 0, -1 };
	if (L <= start && end <= R) return tree[node];
	int mid = (start + end) / 2;
	pair<int, int> left = query(node * 2, start, mid, L, R);
	pair<int, int> right = query(node * 2 + 1, mid + 1, end, L, R);
	if (left.first >= right.first) return left;
	return right;
}

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

	cin >> n;
	for (int i = 0; i < n; i++) cin >> nodes[i];
	build(1, 0, n - 1);
	cin >> m;
	while (m--) {
		int a, b, c; cin >> a >> b >> c;
		if (a == 1) update(1, 0, n - 1, b - 1, c);
		else {
			pair<int, int> max1 = query(1, 0, n - 1, b - 1, c - 1);
			update(1, 0, n - 1, max1.second, 0);
			pair<int, int> max2 = query(1, 0, n - 1, b - 1, c - 1);
			update(1, 0, n - 1, max1.second, max1.first);
			cout << max1.first + max2.first << "\n";
		}
	}
}