[백준oj] 12846번 무서운 아르바이트

www.acmicpc.net/problem/12846

12846번: 무서운 아르바이트

---

 

이 문제는 세그먼트트리를 응용해서, 구간중에 최소값을 저장해두는 세그먼트트리를 구현하여, 구간범위*최소값의 최대값을 구하면되는문제이다. 구간범위의 최소값은 세그먼트트리를 이용하여 구하고, 그 최소값의 최대값은 분할정복을 통해 최대값을 구하면된다.

 

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

long long tree[4*100100];
int arr[100100];
//초기화 겸 업데이트
void init(int st, int end, int node) {
	if (st == end) {
		tree[node] = st;
		return;
	}

	int middle = (st + end)>>1;
	init(st, middle, node * 2);
	init(middle + 1, end, node * 2 + 1);
	if (arr[tree[node * 2]] <= arr[tree[node * 2 + 1]]) {
		tree[node] = tree[node * 2];
	}
	else {
		tree[node] = tree[node * 2 + 1];
	}
}
//최솟값의 위치 리턴
long long min(int st, int end, int node, int l, int r) {
	//범위 밖이면 -1
	if (end < l || r < st) {
		return -1;
	}

	//범위 안이면 return
	if (l <= st && end <= r) {
		return tree[node];
	}

	int middle = (st + end)>>1;
	long long m1 = min(st, middle, node * 2, l, r);
	long long m2 = min(middle + 1, end, node * 2 + 1, l, r);
	if (m1 == -1) {
		return m2;
	}
	else if (m2 == -1) {
		return m1;
	}
	else {
		if (arr[m1] <= arr[m2]) {
			return m1;
		}
		else {
			return m2;
		}
	}
}

long long solve(int l, int r,int n) {
	long long mini = min(0, n - 1, 1, l, r);//l~r까지 최소값 인덱스
	long long result = (long long)(r - l + 1)*(long long)arr[mini];
	//재귀로 분할정복
	if (l <= mini - 1) {
		long long temp = solve(l, mini - 1, n);
		if (temp > result) {
			result = temp;
		}
	}
	if (mini + 1 <= r) {
		long long temp = solve(mini + 1, r, n);
		if (temp > result) {
			result = temp;
		}
	}
	return result;
}


int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL), cout.tie(NULL);
	int n,d;
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> arr[i];
	}
	init(0, n - 1, 1);
	cout << solve(0, n - 1, n);

	return 0;
}