코드 복사/붙여넣기 하는 당신이 아름답습니다.

15561 : 구간 합 최대? 2

풀이

max(U * (K[i] + K[i+1] + ... K[j]) + V * (j - i))

= max(U * (K[i] + K[i+1] + ... K[j]) + V * (j - i + 1)) - V

모든 A[i]U * A[i] + V로 바꿔주면

max(A[i] + ... + A[j])가 최대가 되는 연속 구간 최대 합을 구하는 문제가 된다.

15560번에 비해 범위가 크므로 세그먼트 트리 등등을 이용해주자.

코드

#include <cstdio>
#include <algorithm>
using namespace std;

const int inf = 1e9;

int n, q, u, v, arr[100001];
struct node {
    int ls, rs, lrs, mxs;
    node(int ls=-inf,int rs=-inf,int lrs=0,int mxs=-inf):ls(ls),rs(rs),lrs(lrs),mxs(mxs){}
} tree[400004];

node merge(const node &a, const node &b) {
    node ret;
    ret.ls = max(a.ls, a.lrs + b.ls);
    ret.rs = max(a.rs + b.lrs, b.rs);
    ret.lrs = a.lrs + b.lrs;
    ret.mxs = max({ a.mxs,b.mxs,a.rs+b.ls });
    return ret;
}

void update(int idx, int val, int now, int lft, int rgt) {
    if (idx < lft || rgt < idx) return;
    if (lft == rgt) {
        tree[now] = node(val, val, val, val);
        return;
    }
    update(idx, val, now * 2, lft, (lft + rgt) / 2);
    update(idx, val, now * 2 + 1, (lft + rgt) / 2 + 1, rgt);
    tree[now] = merge(tree[now * 2], tree[now * 2 + 1]);
}

node query(int now, int lft, int rgt, int x, int y) {
    if (rgt < x || y < lft) return node();
    if (x <= lft && rgt <= y) return tree[now];
    node r1 = query(now * 2, lft, (lft + rgt) / 2, x, y);
    node r2 = query(now * 2 + 1, (lft + rgt) / 2 + 1, rgt, x, y);
    return merge(r1, r2);
}

int main() {
    scanf("%d %d %d %d", &n, &q, &u, &v);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &arr[i]);
        update(i, u * arr[i] + v, 1, 1, n);
    }

    while (q--) {
        int c, a, b;
        scanf("%d %d %d", &c, &a, &b);
        if (!c) {
            printf("%d\n", query(1, 1, n, a, b).mxs - v);
        }
        else {
            arr[a] = b;
            update(a, u * b + v, 1, 1, n);
        }
    }

    return 0;
}

아무말

백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge, C, C++, 씨, 씨쁠쁠, JAVA, algorithm, 자바, 알고리즘, 자료구조, 문제, 문제 풀이, 풀이

wookje.kwon's profile image

wookje.kwon

2018-04-12 18:21

Read more posts by this author