[P5] 백준 1989번 부분배열 고르기 2 C++ 세그먼트 트리

리뷰

 

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

[P5] 백준 2104번 부분배열 고르기 C++ 세그먼트 트리

위 문제와 동일하나 구간의 범위까지 출력해 주어야 하는 문제

 

 

전역 변수

• MAX_N : n값의 최대값을 저장할 정수형 상수 변수
• n : 배열의 길이를 저장할 변수
• nodes : 배열의 정보를 저장할 정수형 배열, 크기는 MAX_N
• minTree : 최소값의 인덱스를 저장할 세그먼트 트리, 크기는 MAX_N * 4
• Res : 구간의 합과 해당 구간 정보를 저장할 구조체
• sumTree : 구간의 합을 저장할 Res 타입 세그먼트 트리, 크기는 MAX_N * 4

 

함수

2104번 문제와 동일

다만, 구간합을 구할 때 인덱스를 같이 빼내야 하므로 일부 함수의 리턴값과 세그 트리 초기화 방식이 다르다.

해당부분은 정답 코드를 참조하여 확인하길 바란다.

 

 

문제풀이

2104번 문제와 동일

 

 

참고 사항

• sumTree의 경우 일반 정수형이 아닌 Res타입을 사용하기에 인덱스 관리에도 신경을 써주어야 한다.
• 특히 sumQuery 함수에서 L과 R이 s, e범위를 벗어났을때 처리가 중요하다.
• 내 코드에서는 범위를 벗어난 경우 {0, -1, -1}을 리턴하게 해주었다.
• 따라서 정상적인 값을 리턴할때는 left, right가 범위를 벗어났는지 체크를 진행해 주어야 한다.
• 코드를 보면 알겠지만 left.l이 -1이라면 right.l을, right.r이 -1이라면 left.r을 리턴하는 로직이 있다.

 

정답 코드

#include<iostream>
#define ll long long
using namespace std;

const ll MAX_N = 100000;
ll n;
ll nodes[MAX_N];
ll minTree[MAX_N * 4];
struct Res {
	ll val, l, r;
};
Res sumTree[MAX_N * 4];

void minBuild(ll node, ll s, ll e) {
	if (s == e) minTree[node] = s;
	else {
		ll mid = (s + e) / 2;
		minBuild(node * 2, s, mid);
		minBuild(node * 2 + 1, mid + 1, e);
		minTree[node] = nodes[minTree[node * 2]] <= nodes[minTree[node * 2 + 1]] ? minTree[node * 2] : minTree[node * 2 + 1];
	}
}

void sumBuild(ll node, ll s, ll e) {
	if (s == e) sumTree[node] = { nodes[s], s, e };
	else {
		ll mid = (s + e) / 2;
		sumBuild(node * 2, s, mid);
		sumBuild(node * 2 + 1, mid + 1, e);
		Res left = sumTree[node * 2];
		Res right = sumTree[node * 2 + 1];
		sumTree[node] = { left.val + right.val, left.l, right.r };
	}
}

ll getIndex(ll node, ll s, ll e, ll L, ll R) {
	if (R < s || e < L) return -1;
	if (L <= s && e <= R) return minTree[node];
	ll mid = (s + e) / 2;
	ll left = getIndex(node * 2, s, mid, L, R);
	ll right = getIndex(node * 2 + 1, mid + 1, e, L, R);
	if (left == -1) return right;
	if (right == -1) return left;
	return nodes[left] <= nodes[right] ? left : right;
}

Res sumQuery(ll node, ll s, ll e, ll L, ll R) {
	if (R < s || e < L) return {0, -1, -1};
	if (L <= s && e <= R) return {sumTree[node].val, L, R};
	ll mid = (s + e) / 2;
	Res left = sumQuery(node * 2, s, mid, L, R);
	Res right = sumQuery(node * 2 + 1, mid + 1, e, L, R);
	return { left.val + right.val, left.l != -1 ? left.l : right.l, right.r != -1 ? right.r : left.r };
}

Res minQuery(ll s, ll e) {
	if (s > e) return { 0, -1, -1 };
	ll min_index = getIndex(1, 0, n - 1, s, e);
	Res all = sumQuery(1, 0, n - 1, s, e);
	all.val *= nodes[min_index];
	Res left = minQuery(s, min_index - 1);
	Res right = minQuery(min_index + 1, e);
	if (all.val >= left.val && all.val >= right.val) return all;
	if (left.val >= all.val && left.val >= right.val) return left;
	return right;
}

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

	cin >> n;
	for (ll i = 0; i < n; i++) cin >> nodes[i];
	minBuild(1, 0, n - 1);
	sumBuild(1, 0, n - 1);
	Res result = minQuery(0, n - 1);
	cout << result.val << "\n" << result.l + 1 << " " << result.r + 1;
}