백준 15560 - 구간 합 최대? 1

백준 15560 - 구간 합 최대? 1

풀이

수열 K의 모든 값들을 $K[i] = U*K[i] + V$로 변환한다.

1번 쿼리의 경우, A~B 동안 이동하면서 변환시킨 K 수열에 대한 누적합이 최대가 되도록 만든다.
즉, sum < 0인 경우 굳이 다음 것에 누적시켜줄 필요 없이 sum = 0으로 만들어준다.
최종 결과에서 $V \times (j-i+1)$이 아닌 $V \times (j-i)$이므로 $-V$를 해주면 된다.

2번 쿼리의 경우, $K[A] = U*B + V$ 으로 변환시켜주면 된다.

N,Q가 $10^3$이하이고, 1번 쿼리는 $O(B-A)$으로 $O(10^3)$이고 2번 쿼리는 $O(1)$이다. 따라서 $O(10^6)$에 통과할 수 있다.

코드

#include <bits/stdc++.h>

#define endl "\n"
#define all(v) (v).begin(), (v).end()
#define For_IMPL(condition, i, a, b, increment, decrement) \
    for (ll i = (a); condition; (a < b ? increment : decrement))
#define For(i, a, b) For_IMPL((a < b ? i <= b : i >= b), i, a, b, ++i, --i)
#define ft first
#define sd second

using namespace std;
using ll = long long;
using lll = __int128_t;
using ulll = __uint128_t;
using ull = unsigned long long;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using ti3 = tuple<int, int, int>;
using tl3 = tuple<ll, ll, ll>;

template<class T> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }

const int INF = 987654321;
const int INF0 = numeric_limits<int>::max();
const ll LNF = 987654321987654321;
const ll LNF0 = numeric_limits<ll>::max();

void solve() {
    ll n,q,u,v; cin >> n >> q >> u >> v;
    vector<ll> k(n+1);
    For(i,1,n) {
        cin >> k[i];
        k[i] = u*k[i]+v;
    }

    auto sol = [&](ll a, ll b) {
        ll sum=0, ans=-LNF;
        For(i,a,b) {
            sum += k[i];
            ans = max(ans, sum);
            if(sum < 0) sum = 0;
        }
        return ans;
    };

    while(q--) {
        int c,a,b; cin >> c >> a >> b;
        if(c == 0) cout << sol(a,b)-v << endl;
        else k[a] = u*b + v;
    }
}

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int TC=1;
//    cin >> TC;
    For(tc, 1, TC) {
//        cout << "Case #" << tc << ": ";
        solve();
    }


    return 0;
}