백준 15560 / C++

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

15560번: 구간 합 최대? 1

[ 풀이 ]

식을 정돈하자. 누적합 psum으로 정리하면.. U*(psum[j]-psum[i-1])+V(j-i)이다. 

왠지 U*psum[i]+V*i 를 다시 f(i)로 놓고 싶다. 그러면 식은 f(j)-f(i-1)-V가 된다. 

이제 문제는 구간 [A,B]에서 f(j)-f(i-1)의 최댓값을 구하면 된다. 

O(N)에 해결하자. dp[j]를 f(j)-f(i-1)의 최댓값이라 하자. (j를 고정시킴) 구하는 값은 max(dp[A],....,dp[B])이다. 

스위핑을 하면서 f(i-1)의 최솟값을 계속 갱신하고 f(j)에서 빼주면서 최댓값도 갱신해주면 된다. 

이제 수열의 값을 변경하는 쿼리를 해보자. k[A]를 변경하면, 우리는 누적합을 보고 있으므로, 

psum[A]부터 psum[N]까지 값을 갱신해주면 된다. 역시 O(N)에 해줄 수 있다. 

총 시간복잡도는 O(QN)이다. 

 

[ Code ]

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll n, Q, U, V, C, A, B;
ll a[1001], psum[1001], f[1001];

void query(int C, int A, int B) {
	if (C == 0) {
		ll mini = 1e18;
		ll maxi = -1e18;
		for (int i = A; i <= B; i++) {
			mini = min(mini, f[i - 1]); // min
			maxi = max(maxi, f[i] - mini); // max 
		}
		// max(dp[A],...,dp[B]) - V 
		cout << maxi - V << '\n';
	}
	else {
		// k[A]=B -> psum[A]~psum[B] update , f[A]~f[B] update
		for (int i = A; i <= n; i++) {
			psum[i] += (B - a[A]);
			f[i] += U * (B - a[A]);
		}
		a[A] = B;
	}
}

int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	cin >> n >> Q >> U >> V;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
		psum[i] = psum[i - 1] + a[i];
		f[i] = U * psum[i] + V * i;
	}
	// O(QN) solution 
	while (Q--) {
		cin >> C >> A >> B;
		query(C, A, B);
	}
}