백준 15561 / C++ / 구간합 최댓값 쿼리 O(logN)에 처리하기

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

15561번: 구간 합 최대? 2

[ 풀이 ]

이제 이 문제의 합의 최댓값 구하기를 O(logN)에 처리해보자. 

연속구간합의 최댓값은 잘 알려진 방법을 통해 O(logN)에 처리할 수 있다.

자세한 설명(https://seungwuk98.tistory.com/39) 은 이곳을 참고하자. 

 

[ Code ]

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct Node { ll tot, lsum, rsum, val; };
ll n, Q, U, V, C, A, B, INF = 1e18;

Node merge(Node a, Node b) {
	Node c;
	c.tot = a.tot + b.tot;
	c.lsum = max(a.lsum, a.tot + b.lsum);
	c.rsum = max(b.rsum, b.tot + a.rsum);
	c.val = max({ a.val, b.val, a.rsum + b.lsum });
	return c;
}

struct segment_tree {
	Node tree[400004];
	void upd(int node, int s, int e, int idx, ll v) {
		if (idx<s || idx>e) return;
		if (s == e) {
			tree[node] = { v, v, v, v };
			return;
		}
		int m = (s + e) / 2;
		upd(2 * node, s, m, idx, v);
		upd(2 * node + 1, m + 1, e, idx, v);
		tree[node] = merge(tree[2 * node], tree[2 * node + 1]);
	}

	Node query(int node, int s, int e, int qs, int qe) {
		if (s > qe || e < qs) return { 0, -INF, -INF, -INF };
		if (qs <= s && e <= qe) return tree[node];
		int m = (s + e) / 2;
		Node L = query(2 * node, s, m, qs, qe);
		Node R = query(2 * node + 1, m + 1, e, qs, qe);
		return merge(L, R);
	}
}seg;

int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	cin >> n >> Q >> U >> V;
	for (int i = 1; i <= n; i++) {
		ll x;  cin >> x;
		seg.upd(1, 1, n, i, U * x + V);
	}
	while (Q--) {
		cin >> C >> A >> B;
		if (C == 0) {
			cout << seg.query(1, 1, n, A, B).val - V << '\n';
		}
		else {
			seg.upd(1, 1, n, A, U * B + V);
		}
	}
}