백준 17408 c++ "수열과 쿼리 24" -PlusUltraCode-

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

 

[필자 사고]

이 문제는 세그먼트 트리 자료형을 구해서 풀어야 되는 문제이다.

ㅇㅣ 문제만의 특징은 특정 구간 내에 A1+A2의 최댓값을 구하라는 문제이다.

 

필자는 구간내 최대로 큰 숫자를 가지고 있는 A1을 찾은뒤 idx를 이용하여

해당 idx를 제외한 나머지 범위에 쿼리를 날려 그 중 큰 수를 가지고 있는 A2를 찾는 방식으로

코드를 작성했다. 위와 같은 형태로 구하기 위해서는 트리를 초기화 할때 pair<>을 사용하여

값과 인덱스 모두 저장해야 된다.

두가지 인덱스를 사용해야 된다는 점에서 많은 공부가 된 문제다.

[코드 해설]

1. 입력 처리 및 초기화 (Input 함수)

• 목적: 배열과 세그먼트 트리를 초기화합니다.
  1. 배열 크기 NNN을 입력받습니다.
  2. 배열 arrarrarr에 데이터를 저장합니다.
  3. 세그먼트 트리 treetreetree의 크기를 4N4N4N으로 설정하고 초기화합니다.
  4. 세그먼트 트리를 초기화하는 Init_Tree 함수를 호출합니다.

---

2. 세그먼트 트리 초기화 (Init_Tree 함수)

• 목적: 배열의 값 중 구간 내 최대 값을 효율적으로 찾을 수 있도록 세그먼트 트리를 구성합니다.
  1. 기저 조건: 현재 구간이 하나의 원소를 나타내는 경우, 해당 노드에 배열 값을 저장합니다.
  2. 재귀 처리:
     • 구간을 왼쪽과 오른쪽으로 나누어 각각 초기화합니다.
     • 두 구간의 최대값을 비교하여 현재 노드에 저장합니다.

---

3. 세그먼트 트리 쿼리 처리 (Query 함수)

• 목적: 지정된 범위 [left,right][left, right][left,right]에서 최대 값을 구합니다.
  1. 기저 조건:
     • 현재 구간이 완전히 쿼리 범위에 포함되면, 해당 노드 값을 반환합니다.
     • 현재 구간이 쿼리 범위와 겹치지 않으면, {0,0}\{0, 0\}{0,0}을 반환합니다.
  2. 재귀 처리:
     • 구간을 왼쪽과 오른쪽으로 나누어 각각 쿼리를 수행합니다.
     • 두 결과 중 더 큰 값을 반환합니다.

---

4. 세그먼트 트리 값 업데이트 (Update 함수)

• 목적: 배열 값이 변경될 때, 세그먼트 트리를 갱신합니다.
  1. 기저 조건:
     • 변경하려는 인덱스가 현재 구간에 속하지 않으면 반환합니다.
     • 구간이 단일 원소인 경우, 값을 업데이트합니다.
  2. 재귀 처리:
     • 구간을 나누어 적절한 위치에서 업데이트를 수행합니다.
     • 하위 노드 값을 기반으로 현재 노드 값을 갱신합니다.

---

5. 게임 실행 (Game_Start 함수)

• 목적: 주어진 명령을 처리합니다.
  1. 명령의 종류는 두 가지입니다.
     • 명령 1: 특정 인덱스의 값을 갱신합니다.
     • 명령 2: 주어진 범위에서 가장 큰 두 값을 찾아 합을 출력합니다.
  2. 최대값 두 개를 찾는 방법:
     • 전체 범위에서 최대값과 해당 인덱스를 찾습니다.
     • 해당 인덱스를 제외한 나머지 범위에서 두 번째 최대값을 찾습니다.
  3. 두 값의 합을 출력합니다.

---

6. 메인 함수

• 목적: 프로그램 실행의 시작점입니다.
  1. 입력 데이터를 처리하고 InputInputInput 함수를 호출합니다.
  2. 명령 처리를 위해 GameStartGame_StartGameS​tart 함수를 호출합니다.

[소스 코드]

#include <iostream>
#include <vector>
#include <algorithm>
#define ll long long
#define pll pair<long,int>
using namespace std;

int N, M;
vector<pll> tree;
vector<ll> arr;

void Init_Tree(int node, int start, int end) {
	if (start == end) {
		tree[node] = { arr[start],start };
		return;
	}

	int mid = (start + end) / 2;
	Init_Tree(node * 2, start, mid);
	Init_Tree(node * 2 + 1, mid + 1, end);

	tree[node] = max(tree[node * 2], tree[node * 2 + 1]);
}
pll Query(int node, int start, int end, int left, int right) {
	if (left <= start && end <= right) {
		return tree[node];
	}

	if (end < left || right < start)return { 0,0 };

	int mid = (start + end) / 2;
	pll leftNode = Query(node * 2, start, mid, left, right);
	pll rightNode = Query(node * 2 + 1, mid + 1, end, left, right);

	return (leftNode.first > rightNode.first) ? leftNode : rightNode;
}
void Update(int node, int start, int end, int idx, ll val) {
	if (start == end) {
		tree[node].first = val;
		return;
	}

	if (idx < start || end < idx)return;

	int mid = (start + end) / 2;
	if (idx <= mid) {
		Update(node * 2, start, mid, idx, val);
	}
	else {
		Update(node * 2 + 1, mid + 1, end, idx, val);
	}

	tree[node] = max(tree[node * 2], tree[node * 2 + 1]);
}

void Input() {
	cin >> N;
	tree.resize(N * 4);
	arr.resize(N + 1);
	for (int i = 1; i <= N; i++) {
		cin >> arr[i];
	}
	
	cin >> M;
	Init_Tree(1, 1, N);
}

void Game_Start() {
	for (int i = 1; i <= M; i++) {
		int flag;
		ll param1, param2;
		cin >> flag >> param1 >> param2;

		if (flag == 1) {
			Update(1, 1, N, param1, param2);
		}
		else {
			pll maxTree = Query(1, 1, N, param1, param2);
			int idx = maxTree.second;
			pll secondTree = max(Query(1, 1, N, param1, idx - 1),
								Query(1, 1, N, idx + 1, param2));

			cout << maxTree.first + secondTree.first << '\n';
		}
	}
}

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

	Input();
	Game_Start();
}