[백준 15561번] [세그먼트 트리 / 분할 정복] 구간 합 최대? 2

백준 16993번과 매우 유사하다.

 

다만 차이점이 2개 존재한다.

 

백준 16993번의 경우에는 단순한 금광 세그라면, 이 문제의 경우에는 U와 V를 곱해주는 과정을 수반하게 된다.

추가적으로 이 문제에서는 세그 트리를 중간에 수정함으로써 update과정을 진행해주어야 한다.

 

일단 처음에 고전했던 부분은 U와 V를 곱해주는 과정을 어떻게 처리할 것인지에 대한 아이디어이다.

U의 경우에는 16993번에서 한 결과값에 U만 곱해주면 되는데 V의 경우가 처리하기가 처음에 껄끄러웠다.

 

j - i를 처리해주어야 하기에 처음에는 왼쪽을 기준으로 연산했을 때와 오른쪽을 기준으로 연산했을 때의 갯수를 구조체 안에 넣을 생각을 먼저 했는데 너무 비효율적인 것 같아서 포기하였다.

 

사실 고민을 좀 해보면, V를 처음 init하는 과정에서 모두 포함해주면 해결되는 문제이다.

포함되는 만큼이 V가 들어가기때문에 쉽게 이 부분을 해결할 수 있다.

다만, j - i만큼이 V와 곱해져야하는 상황이므로 전체 갯수 - 1만큼이 V와 곱해진 것과 같다. 따라서 마지막에 출력해줄때만 V를 빼주면 된다.

 

또한 세그 트리를 업데이트 해주는 경우는 해당 index를 포함하고 있지 않은 쿼리는 그대로 기존 쿼리 값을 긁어오면 되고, index를 포함하고 있는 경우에만 트리를 업데이트 해주면 된다.(다만, Base case로 start == end인 경우를 따로 설정해주어야 예외 케이스가 발생하지 않는 점을 유의하도록 하자.)

 

금광 세그의 경우에는 left, right, max, sum(각각 왼쪽에서 시작했을 때의 구간합 최대, 오른쪽에서 시작했을 때의 구간합 최대, 전체 구간합 최대, 해당 쿼리의 전체 원소들의 합)을 구조체로 묶어서 관리해준 뒤 분할정복하여 처리해주는 방식으로 진행하게 된다.

해당 방향성에 대해서 잘 알아두도록 하자.

#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

using namespace std;

int N, Q, U, V;

struct node_data{
    int left;
    int right;
    int max;
    int sum;
    node_data() : left(-123456789), right(-123456789), max(-123456789), sum(0)
    {}
    node_data(int temp1, int temp2, int temp3, int temp4) : left(temp1), right(temp2), max(temp3), sum(temp4)
    {}
};

node_data tree[400001];
int arr[100001];

node_data init(int start, int end, int node){
    if(start == end){
        return tree[node] = node_data(U * arr[start] + V , U * arr[start] + V, U * arr[start] + V, U * arr[start] + V);
    }
    else{
        int mid = (start + end) / 2;
        node_data front = init(start, mid, node * 2);
        node_data back = init(mid + 1, end, node * 2 + 1);
        return tree[node] = node_data(max(front.left, front.sum + back.left), max(front.right + back.sum, back.right), max(max(front.max, back.max), front.right + back.left), front.sum + back.sum);
    }
}

node_data max_query(int start, int end, int left, int right, int node){
    if(right < start || end < left) return node_data(-123456789, -123456789, -123456789, 0);
    if(left <= start && end <= right) return tree[node];
    
    int mid = (start + end) / 2;
    
    node_data front = max_query(start, mid, left, right, node * 2);
    node_data back = max_query(mid + 1, end, left, right, node * 2 + 1);
    return node_data(max(front.left, front.sum + back.left), max(front.right + back.sum, back.right), max(max(front.max, back.max), front.right + back.left), front.sum + back.sum);
}

node_data change(int start, int end, int index, int node){
    if(index < start || end < index) return tree[node];
    if(start == end) return tree[node] = node_data(U * arr[start] + V , U * arr[start] + V, U * arr[start] + V, U * arr[start] + V);
    int mid = (start + end) / 2;

    node_data front = change(start, mid, index, node * 2);
    node_data back = change(mid + 1, end, index, node * 2 + 1);
    return tree[node] = node_data(max(front.left, front.sum + back.left), max(front.right + back.sum, back.right), max(max(front.max, back.max), front.right + back.left), front.sum + back.sum);
}

int main(void){
    fastio;
    memset(tree, 0, sizeof(tree));
    memset(arr, 0, sizeof(arr));

    cin >> N >> Q >> U >> V;

    for(int i = 0; i < N; i++){
        cin >> arr[i];
    }

    init(0, N - 1, 1);
    
    for(int i = 0; i < Q; i++){
        int check_num;
        cin >> check_num;
        if(check_num == 0){
            int query_start, query_end;
            cin >> query_start >> query_end;
            cout << max_query(0, N - 1, query_start - 1, query_end - 1, 1).max - V << "\n";
        }
        else{
            int change_index, change_num;
            cin >> change_index >> change_num;
            arr[change_index - 1] = change_num;
            change(0, N - 1, change_index - 1, 1);
        }
        
    }

    return 0;
}

(처음에 귀찮아서 무식하게 세그 원소 수정할 때마다 트리를 새우는 방식으로 한 것은 안비밀..)