BOJ 25639 수열과 최대 상승 쿼리

문제 링크입니다.

수열 나누기

수열 전체를 적당히 둘로 쪼개면, 그 두 조각에 걸쳐서 상승할 수 있는 최댓값은 오른쪽 조각의 최댓값 - 왼쪽 조각의 최솟값입니다. 나머지 경우는 왼쪽 조각 안에서의 최대 상승 값과, 오른쪽 조각 안에서의 최대 상승 값을 구해 주면 되겠네요. 셋 중 가장 큰 값이 정답이 되고, 각 조각에서의 최대 상승 값은 마찬가지로 그 조각을 둘로 쪼갠 뒤에 구할 수 있습니다.

자구 비빔밥

단일 값을 변경하는 업데이트가 주어집니다. 구간 최솟값/최댓값/최대 상승값을 관리하는 세그먼트 트리를 만들어 업데이트와 쿼리를 각각 $\mathcal{O}(\log N)$, $\mathcal{O}(1)$에 처리해 줍시다.

코드

#include<bits/stdc++.h>
#define mid (l+r>>1)
using namespace std;
using ll = long long;
struct node{
	int mn, mx, ans;
};

node tree[404040];

void upd(int now, int l, int r, int i, int v){
	if(i < l || r < i) return;
	if(l == r){
		tree[now].mn = tree[now].mx = v;
		tree[now].ans = 0;
		return;
	}
	upd(now<<1, l, mid, i, v);
	upd(now<<1|1, mid+1, r, i, v);
	tree[now].mn = min(tree[now<<1].mn, tree[now<<1|1].mn);
	tree[now].mx = max(tree[now<<1].mx, tree[now<<1|1].mx);
	tree[now].ans = max({tree[now<<1].ans, tree[now<<1|1].ans, tree[now<<1|1].mx-tree[now<<1].mn});
	return;
}

node qry(int now, int l, int r, int L, int R){
	if(l > R || L > r) return {1000000007, -1000000007, 0};
	if(L <= l && r <= R) return tree[now];
	node lt = qry(now<<1, l, mid, L, R);
	node rt = qry(now<<1|1, mid+1, r, L, R);
	return {min(lt.mn, rt.mn), max(lt.mx, rt.mx), max({lt.ans, rt.ans, rt.mx-lt.mn})};
}

int main(){
	cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);
	int n; cin >> n; for(int i = 1; i <= n; i++){
		int a; cin >> a; upd(1, 1, n, i, a);
	}
	int Q; cin >> Q; while(Q--){
		int q; cin >> q;
		if(q == 1){
			int k, x; cin >> k >> x; upd(1, 1, n, k, x);
		}
		if(q == 2){
			int L, R; cin >> L >> R; cout << qry(1, 1, n, L, R).ans << '\n';
		}
	}
}