[백준 15561번] 구간 합 최대? 2

---

15561번: 구간 합 최대? 2

---

 

목차

• 사전 지식
• 문제 풀이

 

 

사전 지식

• 세그먼트 트리(Segment Tree)에 대한 기본 지식을 알고 있어야 한다. (링크)
• 가장 큰 연속합을 구하는 세그트리 문제를 이해하고 있어야 한다. (링크)

 

 

 

문제 풀이

$\small{U \times (K_i + K_{i+1} + \cdots + K_j) + V \times (j-i)}$ 의미

이 식은 $\small{(UK_i + UK_{i+1} + \cdots + UK_j) + \sum_{k=i}^{j-1} V}$ 로 나타낼 수 있으며

조금 더 변환하면 $\small{(UK_i+V) + (UK_{i+1}+V) + \cdots + (UK_j+V) - V}$ 로 나타낼 수 있다.

 

즉, 각 원소를 $K_i$가 아닌 $UK_i+V$로 바꾼 배열을 arr이라고 하면 문제의 쿼리를 다음과 같이 재해석할 수 있다.

구간 $\small{[A, B]}$에 대해, arr에서 가장 큰 연속합을 구한다.

어떤 배열에 대해 가장 큰 연속합을 구하는 테크닉은 여기를 참조하기 바란다.

 

	// BOJ 15561
	// Struct SegTree
	#include <bits/stdc++.h>
	using namespace std;
	using ll = long long;
	ll INF = 1e12;
	struct node {
	ll lmax, rmax, max, sum;
	};
	ll sz;
	vector<node> tree;
	node merge(node &l, node &r) {
	node ret;
	ret.lmax = max(l.lmax, l.sum+r.lmax);
	ret.rmax = max(r.rmax, r.sum+l.rmax);
	ret.max = max({l.max, r.max, l.rmax+r.lmax});
	ret.sum = l.sum + r.sum;
	return ret;
	}
	void update(ll idx, ll x) {
	idx += sz;
	tree[idx] = {x, x, x, x};
	while (idx /= 2) tree[idx] = merge(tree[2*idx], tree[2*idx+1]);
	}
	ll query(ll a, ll b) {
	a += sz; b += sz;
	if (a == b) return tree[a].max;
	node left = tree[a];
	node right = tree[b];
	while (a < b) {
	if (b-a == 1) break;
	if (a%2 == 1) left = merge(left, tree[++a]);
	if (b%2 == 0) right = merge(tree[--b], right);
	if (b-a == 1) break;
	left = merge(left, tree[a+1]);
	right = merge(tree[b-1], right);
	a /= 2; b /= 2;
	}
	return merge(left, right).max;
	}
	int main()
	{
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	ll N, Q, U, V; cin >> N >> Q >> U >> V;
	sz = (1 << (ll)ceil(log2(N)));
	tree.assign(2*sz, {-INF, -INF, -INF, 0});
	for (ll i=0; i<N; i++) {
	ll x; cin >> x;
	update(i, U*x + V);
	}
	while (Q--) {
	ll op, a, b; cin >> op >> a >> b;
	if (op == 0) {
	cout << query(a-1, b-1) - V << '\n';
	}
	if (op == 1) {
	update(a-1, U*b + V);
	}
	}
	return 0;
	}

view raw 15561.cpp hosted with ❤ by GitHub