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

 

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

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

 

문제 요약

길이가 N인 수열 $a_1, a_2, \cdots, a_N$에 두 가지의 쿼리를 수행하는 문제이다.
주어지는 쿼리는 다음과 같다.

• $1  k  x : a_k$를 $x$로 바꾼다.
• $2  l  r :$ 구간 $[l,r]$의 최대 상승값을 출력한다.

 

구간 $[l,r]$의 최대 상승값 : $max(a_j-a_i)\quad(l\le i\le j\le r)$

 

접근

세그먼트 트리의 정점들을 '노드'라는 구조체를 선언하여 각 노드에 해당 구간에서의 최댓값, 최솟값, 최대 상승값을 저장하도록 구성했다. 이렇게 구성하면 세그먼트 트리의 말단 노드에는 최댓값, 최솟값에 인덱스 번호에 해당하는 수열의 값이 들어가고, 최대 상승값으로는 0이 들어가게 된다.

merge_node라는 함수를 만들어, 두 구간을 합친 구간에서의 새로운 최댓값, 최솟값, 최대 상승값을 저장한 노드를 반환하게 했다.

왼쪽 구간의 노드를 a, 오른쪽 구간의 노드를 b, 합쳐지는 구간의 노드를 c라고 하자.
merge_node함수는 인자로 a, b를 받아 c를 리턴해준다.

최댓값, 최솟값은 당연히 각각 $max($a$.max,$b$.max)$, $min($a$.min,$b$.min)$가 되고,
최대 상승값은 아래 3가지 경우가 될 수 있다.

 

1. 왼쪽 구간의 최대 상승값이 최대인 경우
2. 오른쪽 구간의 최대 상승값이 최대인 경우
3. (오른쪽 구간의 최댓값) - (왼쪽 구간의 최솟값)이 최대인 경우

3개 중 최댓값을 구해 새 구간의 최대 상승값으로 초기화한다.

이제 구간의 최대 상승값을 찾을 수 있게 되었으니 나머지는 기본적인 세그먼트 트리 구현과 동일하다.

$a_k$를 $x$로 바꾸는 점 쿼리 구현 및 최대 상승값을 구해주는 구간 쿼리를 구현하면 된다.

 

#include <iostream>
using namespace std;

struct node {
	int mn, mx, res;
};

int tree[100001]{};
node seg[262145]{};
int N, M, o, a, b;

node merge_node(node a, node b) {
	node c;
	c.res = max(b.mx - a.mn, max(a.res, b.res));
	c.mx = max(a.mx, b.mx);
	c.mn = min(a.mn, b.mn);
	return c;
}

void init(int s, int e, int n) {
	if (s == e) {
		seg[n].mn = seg[n].mx = tree[s];
		seg[n].res = 0;
		return;
	}
	int m = (s + e) / 2;
	init(s, m, n * 2);	init(m + 1, e, n * 2 + 1);
	seg[n] = merge_node(seg[n * 2], seg[n * 2 + 1]);
}

void upt(int s, int e, int i, int v, int n) {
	if (s == e) {
		seg[n].mn = v;
		seg[n].mx = v;
		seg[n].res = 0;
		return;
	}
	int m = (s + e) / 2;
	if (i <= m)	upt(s, m, i, v, n * 2);
	else	upt(m + 1, e, i, v, n * 2 + 1);
	seg[n] = merge_node(seg[n * 2], seg[n * 2 + 1]);
}

node find(int s, int e, int l, int r, int n) {
	if (l > e || r < s) {
		node c;
		c.mx = -1000000000;
		c.mn = 1000000000;
		c.res = -1;
		return c;
	}
	if (l <= s && e <= r)	return seg[n];
	int m = (s + e) / 2;
	return merge_node(find(s, m, l, r, n * 2), find(m + 1, e, l, r, n * 2 + 1));
}

int main() {
	cin.tie(0)->sync_with_stdio(0);
	cin >> N;
	for (int i = 1; i <= N; i++)	cin >> tree[i];
	init(1, N, 1);
	for (cin >> M; M--;) {
		cin >> o >> a >> b;
		if (o == 1)	upt(1, N, a, b, 1);
		else {
			node ans = find(1, N, a, b, 1);
			cout << ans.res << '\n';
		}
	}
}