[BOJ 25639 // C++] 수열과 최대 상승 쿼리

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 25639번 문제인 수열과 최대 상승 쿼리이다.
문제는 아래 링크를 확인하자.

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

25639번: 수열과 최대 상승 쿼리

한 구간 [L,R]에서 L<=mid<R일 때, "최대 상승값"은 max(([L,mid]에서의 최대 상승값), [mid+1,R]에서의 최대 상승값), ([mid+1,R]구간의 값의 최댓값) - ([L,mid]구간의 값의 최솟값))으로 나누어 생각할 수 있다.

 

위와 같이 경우를 나누면 이 문제는 각 구간의 최댓값, 최솟값 및 최대 상승값을 관리하는 세그먼트 트리를 구현하는 것으로 해결할 수 있게 된다.

 

아래는 제출한 소스코드이다.

#include <iostream>
using namespace std;

int N;
int arr[100001];

struct node {
	int mn, mx, val;
	node() {};
	node(int mn, int mx, int val) {
		this->mn = mn, this->mx = mx, this->val = val;
	}
}seg[262145];

node init(int L, int R, int sI) {
	if (L == R) return seg[sI] = node(arr[L], arr[L], 0);
	node n1 = init(L, (L + R) / 2, sI * 2), n2 = init((L + R) / 2 + 1, R, sI * 2 + 1);
	return seg[sI] = node(min(n1.mn, n2.mn), max(n1.mx, n2.mx), max(n2.mx - n1.mn, max(n1.val, n2.val)));
}

node upd(int L, int R, int qI, int qVal, int sI) {
	if (R < qI || qI < L) return seg[sI];
	if (L == R) return seg[sI] = node(qVal, qVal, 0);
	node n1 = upd(L, (L + R) / 2, qI, qVal, sI * 2), n2 = upd((L + R) / 2 + 1, R, qI, qVal, sI * 2 + 1);
	return seg[sI] = node(min(n1.mn, n2.mn), max(n1.mx, n2.mx), max(n2.mx - n1.mn, max(n1.val, n2.val)));
}

node qry(int L, int R, int qL, int qR, int sI) {
	if (R < qL || qR < L) return node(1000000007, -1000000007, 0);
	if (qL <= L && R <= qR) return seg[sI];
	node n1 = qry(L, (L + R) / 2, qL, qR, sI * 2), n2 = qry((L + R) / 2 + 1, R, qL, qR, sI * 2 + 1);
	return node(min(n1.mn, n2.mn), max(n1.mx, n2.mx), max(n2.mx - n1.mn, max(n1.val, n2.val)));
}

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

	cin >> N;
	for (int i = 1; i <= N; i++) cin >> arr[i];

	init(1, N, 1);

	int Q; cin >> Q;
	while (Q--) {
		int q; cin >> q;
		if (q == 1) {
			int k, x; cin >> k >> x;
			upd(1, N, k, x, 1);
		}
		else {
			int l, r; cin >> l >> r;
			cout << qry(1, N, l, r, 1).val << '\n';
		}
	}
}